codeforces 492C. Vanya and Exams 解题报告

题目链接：http://codeforces.com/problemset/problem/492/C

题目意思：给出 3 个整数：n，  r，  avg。然后有 n 行，每行有两个数：第 i 行有 ai 和 bi。表示如果写 bi 篇文章那么可以在 ai 这个分数上增加 1 分。可以增加好多次，但是前提是加完得到的分数不能超过 r。要使得 n 个exam 的分数平均分至少达到avg时需要写的最少文章是多少篇。

解决方法很简单，贪心即可。

　　 我们当然希望写的文章越少越好，所以先对文章从小到大排序。然后尽量往这个exam的分数加分，直到到达上限 r 。最后的情况是不需要到达 r 时，就把剩余的加上即可，就是代码中的else 循环的：ans += need * exam[i].b;

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 const int maxn = 1e5 + ;

 struct node

 {

     LL a, b;

 }exam[maxn];

 LL cmp(node x, node y)

 {

     if (x.b == y.b)

         return x.a < y.a;

     return x.b < y.b;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     LL n, r, avg;

     LL has, need, needed;

     while (scanf("%I64d%I64d%I64d", &n, &r, &avg) != EOF)

     {

         has = ;

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

         {

             scanf("%I64d%I64d", &exam[i].a, &exam[i].b);

             has += exam[i].a;

         }

         sort(exam, exam+n, cmp);

         LL needed = 1ll * avg * n;

         LL need = 1ll*needed - 1ll*has;

         if (need <= )

             printf("0\n");

         else

         {

             LL ans = ;

             for (LL i = ; i < n && need > ; i++)

             {

                 if ((r-exam[i].a) <= need)

                 {

                     ans += (r-exam[i].a) * exam[i].b;

                     need -= r-exam[i].a;

                 }

                 else

                 {

                     ans += need * exam[i].b;

                     need -= need;

                 }

             }

             printf("%I64d\n", ans);

         }

     }

     return ;

 }