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

题目链接：Towers

Towers

テストごとの時間制限

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ご存知のとおり、バーランドの子供たちはみんなキューブで遊ぶのが大好きです。 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

Note

In最初のサンプルでは、​​2 番目のタワーから 3 番目のタワーへ、そして 2 番目のタワーから最初のタワーへと、キューブを 2 回移動する必要があります。すると、塔の高さはすべて同じで 6 に等しくなります。層は、操作が実行する最大数ｋを求め、操作を経た後、最高の塔と最低の塔の間の高さの差が最小となり、方法を移して印刷される。 .塔の高さの差が 2 より小さい場合、終了します (最適な解決策が得られたため、2 より小さい場合、再移動すると繰り返され、現在の状態よりも低くなります)。 １、最小タムの高さが追加され、最大タムと最小タムの番号がそれぞれ記録され、同時に操作回数ｔ＞＝ｋのとき、主な時間は終了する。 、ただ要遍历一遍数組、即可。

#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;#define INF 0x7fffffffconst int maxn = 1005;typedef struct{    int x,y;}T;T t[maxn], tt[maxn];int main(){    #ifdef sxk        freopen("in.txt","r",stdin);    #endif    int n,k,ch;    while(scanf("%d%d",&n,&k)!=EOF)    {        for(int i=1; i<=n; i++){            scanf("%d", &ch);            t[i].x = i;            t[i].y = ch;        }        memset(tt,0,sizeof(tt));        int my, mx, mmy, mmx;        int cnt = 0;        while(1){            my = 1234567;  mx = 0;  mmy = -1234567;  mmx = 0;            for(int i=1; i<=n; i++){                if(t[i].y < my){                    my = t[i].y;                    mx = t[i].x;                }                if(t[i].y > mmy){                    mmy = t[i].y;                    mmx = t[i].x;                }            }            if(mmy - my < 2 || k<1)  break;            else{                tt[cnt].x = mmx;                tt[cnt++].y = mx;                t[mmx].y --;                t[mx].y ++;                k --;            }        }        printf("%d %d\n", mmy - my, cnt);        if(cnt){            for(int i=0; i<cnt; i++)                printf("%d %d\n", tt[i].x, tt[i].y);            printf("\n");        }    }    return 0;}