锐客网

  1. 首页 > 睿知 > it技术 > >

Codeforces461AAppleman and Toastman 贪心

IT知识codeforces

相逢意气为君饮，系马高楼垂柳边。这篇文章主要讲述Codeforces461AAppleman and Toastman 贪心相关的知识，希望能为你提供帮助。
【Codeforces461AAppleman and Toastman 贪心】        题目大意是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\n" , res); return 0; }







    推荐阅读


    上一篇：（转)获取 request 中用POST方式&quot;Content-type&quot;是&quot;application/x-www-form-urlencoded;charset=utf-8

    下一篇：hdu6049---Sdjpx Is Happy(区间DP+枚举)