题目链接：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 ;
}