题意：
给出n个数，让你用最少次数把所有的数都摞成一堆。
其中当把arr[i]摞在第j堆上时，得扣分arr[i]
题目有要求每个数上面不许摞超过k次，有m个k，让你求出m种情况下限制为k时的最优解，即最少扣分。
思路：
经过多次推算会发现，如果要最后扣分最少，则应该尽量让arr[i]小的摞的次数比较多，而arr[i]大的摞的次数比较少。
然后还有一个规律是，如果想让扣分最少，那每次应该尽量让值大的堆上摞的次数比较多，本身则尽量少摞。即尽量满足 一次摞足够多的物品。
Tips：
如果k = 1，则答案就是arr[1] + (arr[1]+arr[2]) + (arr[1]+arr[2]+arr[3]) + (arr[1] +...+arr[i]) + (arr[1]+...+arr[i]+...+arr[n-1])//因为最后且最大的一摞不用动~所以只需要加到arr[n-1]
否则答案就是一次摞尽量多的物品，为了令大的物品移动尽量少的次数，我们从倒数第二个到倒数第k+1个开始算，arr[n-1]~arr[n-1-k]只需要移动一次，arr[n-1-k]~arr[n-1-k-k*k]只要移动2次..and so on~~//因为1个上面可以摞k个..所以k个上面可以摞k*k个..所以以倍数的方式递增..
优化的方法是先计算出从第0个到第i个的和，这样就可以算出其中任意一段的和了。
所以答案就是while循环算出来的..
Code：
View Code
1 #include <stdio.h> 2 #include <cstring> 3 #include <algorithm> 4 #include <ctime> 5 using namespace std; 6 7 long long sum[100010]; 8 long long arr[100010]; 9 10 int main() 11 { 12 int n, q, k; 13 long long ans, tans, tk; 14 int tmp, tn; 15 while(EOF != scanf("%d", &n)) { 16 tans = 0; 17 for(int i = 1; i <= n; ++i) 18 scanf("%lld", &arr[i]); 19 //printf("_\n"); 20 sort(arr+1, arr+n+1); 21 sum[0] = 0; 22 for(int i = 1; i <= n; ++i) { 23 sum[i] = sum[i-1]+arr[i]; 24 if(i != n) tans += sum[i]; 25 } 26 scanf("%d", &q); 27 while(q--) { 28 ans = 0; 29 tmp = 1; 30 tn = n-1; 31 scanf("%d", &k); 32 // printf("%d__\n",k); 33 tk = k; 34 if(k != 1) { 35 while(tn >= tk) { 36 ans += (sum[tn]-sum[tn-tk])*tmp; 37 tn -= tk; 38 tk *= k; 39 tmp++; 40 } 41 ans += (sum[tn]-sum[0])*tmp; 42 } else ans = tans; 43 printf("%lld%c", ans, q != 0?' ':'\n'); 44 } 45 } 46 return 0; 47 }
链接：http://www.codeforces.com/problemset/problem/226/B