Codeforces461A Appleman and Toastman 贪心
来源：程序员人生 发布时间：2014-09-12 00:36:21 阅读次数：3038次
题目大意是Appleman每次将Toastman给他的Ni个数拆分成两部分后再还给Toastman，若Ni == 1则直接丢弃不拆分，而Toastman将每次获得的Mi个数累加起来作为分数，初始时Toastman直接获得N个数，求Toastman最后能够获得的最高分是多少。
这题简单的贪心，Appleman每次拆分的时候，将最小的一个数作为一部分，剩下的作为另外一部分，这样可以使得较大的数尽量多次参与累加。
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
int values[500001];
long long sums[500001];
int compp(const void* a1, const void* a2)
{
return *((int*)a2) - *((int*)a1);
}
int main()
{
#ifdef _DEBUG
freopen("e:in.txt", "r", stdin);
#endif // _DEBUG
int n;
scanf("%d", &n);
for (int i = 0; i < n;i++)
{
scanf("%d", &values[i]);
}
qsort(values, n, sizeof(int), compp);
sums[0] = values[0];
for (int i = 1; i < n;i++)
{
sums[i] = sums[i - 1] + values[i];
}
long long res = sums[n - 1];
for (int i = n - 1; i >= 1;i--)
{
res += sums[i];
}
printf("%I64d
", res);
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
