Codeforces461A Appleman and Toastman 貪心
來源：程序員人生 發布時間：2014-09-12 00:36:21 閱讀次數：3239次
題目大意是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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
