codeforces 479B Towers 解题报告

题目链接：http://codeforces.com/problemset/problem/479/B

题目意思：有 n 座塔，第 i 座塔有 ai 个cubes在上面。规定每一次操作是从最多 cubes 的塔中取走一个cube，加去拥有最少 cubes 的塔上，那么显然，本来是最多cubes的塔的 cubes 数目会减少1，而拥有最少的 cubes 的塔的cubes数增加 1 。现在最多操作 k 次，使得最多 cubes 数 的塔的cubes数 减去 最少cubes数的塔的cubes 数最少（即题目中的instability）。输出总共执行的次数和具体的移动方案（i j：表示将第 i 个塔的一个cube 加到 第 j 座塔上）

这道题其实很简单，比赛的时候想复杂了，以为需要一个 pre 记录前一次最多cubes - 最少cubes 的数目，于是死改～～～死改～～～～越改越复杂～～～～最终就呵呵啦。

可以这样想，对于每一次移动，我们当然是按题目要求来做：最多cubes - 最少cubes，然后将相应编号的 tower 的 cubes 数作相应的改动（分别为-1，+1），然后再排序，再这样处理。关键是知道什么时候结束！！！就是最多cubes - 最少cubes == 0 的时候。除了这种情况，我们都执行 k 次，因为题目中并没有限制执行次数尽量少，而只是希望instability尽量少而已。那么即使有些情况重复执行也是不影响最终结果的！！

还有一个特判就是如果刚开始的时候最多cubes - 最少cubes == 0了，我们就不需要作任何操作，直接输出0 0 即可。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int N =  + ;

 #define f first

 #define s second

 pair<int, int> p[maxn];

 int ans[N][];

 int main()

 {

     int n, k;

     while (scanf("%d%d", &n, &k) != EOF)

     {

         for (int i = ; i <= n; i++)

         {

             scanf("%d", &p[i].f);

             p[i].s = i;

         }

         sort(p+, p++n);

         if (p[n].f == p[].f)

             printf("0 0\n");

         else

         {

             int cnt = ;

             for (int l = ; l < k; l++)

             {

                 ans[cnt][] = p[n].s;      // 记录编号

                 ans[cnt++][] = p[].s;

                 p[n].f--;

                 p[].f++;

                 sort(p+, p++n);

                 if (p[n].f == p[].f)      // 最多cubes == 最少cubes

                     break;

             }

             printf("%d %d\n", p[n].f - p[].f, cnt);

             for (int i = ; i < cnt; i++)

                 printf("%d %d\n", ans[i][], ans[i][]);

         }

     }

     return ;

 }