Codeforces ラウンド #274 (ディビジョン 2) B. Towers_html/css_WEB-ITnose

ご存知のとおり、バーランドの子供たちはみんなキューブで遊ぶのが大好きです。 Little Petya には、同じサイズの立方体で構成される n 個の塔があります。番号 i のタワーは、積み重ねられた AI キューブで構成されています。 Petya は、一連の塔の不安定性を、塔の最高の高さと最低の高さの差に等しい値として定義しています。たとえば、Petya が高さ (8、3、2、6、3) の 5 つの立方体タワーを構築した場合、このセットの不安定性は 6 に等しくなります (最も高いタワーの高さは 8、最も低いタワーの高さは 2)。少年は、一連の塔の不安定性をできるだけ低くしたいと考えています。彼にできることは、次の操作を数回実行することだけです。あるタワーから一番上のキューブを取り出し、それをセットの他のタワーの上に置きます。 Petya は時間の無駄だと考えているため、キューブを取り外されたのと同じタワーには決して置かないことに注意してください。

学校に行く前に、少年はそのような操作を k 回しか実行する時間がありません。 Petya は授業に遅刻したくないので、あなたは彼がこのタスクを達成できるように手伝ってあげる必要があります。

入力

最初の行には、スペースで区切られた 2 つの正の整数 n と k (1?≤?n?≤?100) が含まれています。 , 1?≤?k?≤?1000)?指定されたセット内のタワーの数と、Petya が実行できる操作の最大数。 2 行目には、n 個のスペースで区切られた正の整数、ai (1?≤?ai?≤?104) が含まれています。塔の初期の高さ。

出力

最初の行には、スペースで区切られた 2 つの非負の整数 s と m (m?≤?k) を出力します。最初の数値は、最大 k 個の操作を実行した後に取得できる最小の不安定性の値であり、2 番目の数値は、そのために必要な操作の数です。

次の m 行では、各操作の説明を 2 つの正の値として出力します。整数 i と j、それぞれは 1 から n までの制限内にあります。これらは、Petya が i 番目のタワーから一番上のキューブを取り出し、j 番目のタワーに置いたことを表します (i?≠?j)。操作を実行する過程で、一部のタワーの高さがゼロになる可能性があることに注意してください。

可能な限り最小限の不安定性が達成される正しいシーケンスが複数ある場合は、それらのいずれかを印刷することができます。

サンプルテスト

入力

3 25 8 5

出力

0 22 12 3

入力

3 42 2 4

出力

1 13 2

入力

5 38 3 2 6 3

出力

3 31 31 21 3

题意： 给出n各塔は、[i] 個のスタックから構成され、システム全体の安定度は、k 回移動可能な最大の高さから、k 回の移動で得られる最小の高さである。

思路：模拟

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1005;struct Node {	int x, id;} node[maxn];struct Op {	int x, y;} q[maxn];int ans[maxn];bool cmp(Node a, Node b) {	return a.x < b.x;}int main() {	int n, k;	scanf("%d%d", &n, &k);	for (int i = 1; i <= n; i++) {		scanf("%d", &node[i].x);		node[i].id = i;	}	sort(node+1, node+1+n, cmp);	ans[0] = node[n].x - node[1].x;	for (int i = 1; i <= k; i++) {		sort(node+1, node+1+n, cmp);		node[1].x++, node[n].x--;		q[i].y = node[1].id, q[i].x = node[n].id;		sort(node+1, node+1+n, cmp);		ans[i] = node[n].x - node[1].x;	}	int pos = 0, Max = ans[0];	for (int i = 1; i <= k; i++)		if (ans[i] < Max)			Max = ans[i], pos = i;	printf("%d %d\n", Max, pos);	for (int i = 1; i <= pos; i++)		printf("%d %d\n", q[i].x, q[i].y);	return 0;}