codeforces C. New Year Ratings Change 解题报告

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

题目意思：有n个users，每个user都有自己想升的rating。要解决的问题是给予每个人不同的rating，使得每个人rating不比他期望的rating小，即安排的rating >= 他自己的希望的rating，还有一个条件就是总rating之和要最小。

要想使得总rating最少，那么安排的rating要尽可能小。把rating从小到大排序。对最小的rating值当然就给予这个值，于是下一次安排的rating在这个值的基础下递增1（rmin+1），当下一个user期望的rating和这个值相同时，就把rmin+1分配给他，接着下一次安排的最小rating是rmin+2。当遇到期望的rating比这个安排的rating要大时，安排的rating恰好可以安排他所期望的，而下一次安排的rating的值是他自己希望的rating+1

由于要按顺序把这些rating输出，还要附加一个id值表明这些user初始的位置。

Time	Memory

717 ms

3500 KB

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = *1e5 + ;

 struct ratings

 {

     int id;

     int ra;

     int ans;

 } exp[maxn];

 int cmpid(ratings x, ratings y)

 {

     return x.id < y.id;   // id从小到大排序

 }

 int cmpra(ratings x, ratings y)

 {

     return x.ra < y.ra;   // ra从小到大排序

 }

 int main()

 {

     int i, n;

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

     {

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

         {

             scanf("%d", &exp[i].ra);

             exp[i].id = i;

         }

         sort(exp+, exp+n+, cmpra);

         int cur = exp[].ra;

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

         {

             if (exp[i].ra <= cur)

             {

                 exp[i].ans = cur;

                 cur++;

             }

             else

             {

                 exp[i].ans = exp[i].ra;

                 cur = exp[i].ra + ;

             }

         }

         sort(exp+, exp+n+, cmpid);

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

             printf("%d ", exp[i].ans);

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

     }

     return ;

 }

参考人家写的，pair原来这么强大的！！！ ^_^

Time	Memory

171 ms

3500 KB

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define f first

 #define s second

 #define max(a, b) ((a) > (b) ? (a) : (b))

 const int maxn = *1e5 + ;

 pair<int, int> p[maxn];

 int ans[maxn];

 int main()

 {

     int i, n, cur;

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

     {

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

         {

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

             p[i].s = i;

         }

         sort(p+, p+n+);

         cur = ;

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

         {

             cur = max(p[i].f, cur+);

             ans[p[i].s] = cur;

         }

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

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

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

     }

     return ;

 }

巴特西

codeforces C. New Year Ratings Change 解题报告

最新文章

热门文章