题目：http://codeforces.com/problemset/problem/227/D
题意：n堆个数石子，每堆石子有ai个，通过合并（即将一堆石子移到另一堆石子上），将所有石子合并为一堆，每次合并的代价是这堆石子的个数，在ki的限制下，每堆石子最多只能被合并k次，k次之后就必须移动该堆石子到别的堆上，求合并到最后的总的最小代价。
题解：emmmmm，既然是找最小代价，那么石子个数最多的那堆石子肯定是不移动的，把个数次小的k堆石子移动到这堆石子上，所以这k堆石子移动了一次，这k堆石子中的每一个又是比他们小的k堆石子合并到它们身上的，即这k*k堆移动了两次，以此类推:
k 1次
k*k 2次
k*k*k 3次
k*k*k*k 4次
.
.
.
.
所以总代价最小即是k*1*个数+k^2*2*个数+k^3*3*个数.....
当然k为1时需要特判，最小堆移动了n-1次，次小堆移动n-2次，最大堆不动，具体看代码。
注意大部分数据都是long long 范围。
1 #include <map> 2 #include <stack> 3 #include <queue> 4 #include <cmath> 5 #include <string> 6 #include <limits> 7 #include <cstdio> 8 #include <vector> 9 #include <cstdlib> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 #define Scc(c) scanf("%c",&c) 14 #define Scs(s) scanf("%s",s) 15 #define Sci(x) scanf("%d",&x) 16 #define Sci2(x, y) scanf("%d%d",&x,&y) 17 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z) 18 #define Scl(x) scanf("%I64d",&x) 19 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y) 20 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z) 21 #define Pri(x) printf("%d ",x) 22 #define Prl(x) printf("%I64d ",x) 23 #define Prc(c) printf("%c ",c) 24 #define Prs(s) printf("%s ",s) 25 #define For(i,x,y) for(int i=x;i<y;i++) 26 #define For_(i,x,y) for(int i=x;i<=y;i++) 27 #define FFor(i,x,y) for(int i=x;i>y;i--) 28 #define FFor_(i,x,y) for(int i=x;i>=y;i--) 29 #define Mem(f, x) memset(f,x,sizeof(f)) 30 #define LL long long 31 #define ULL unsigned long long 32 #define MAXSIZE 100005 33 #define INF 0x3f3f3f3f 34 const int mod=1e9+7; 35 const double PI = acos(-1.0); 36 37 using namespace std; 38 int cmp(LL a,LL b) 39 { 40 return a<b; 41 } 42 int main() 43 { 44 45 LL n; 46 Scl(n); 47 int i; 48 LL a[MAXSIZE]= {0}; 49 for (i=1; i<=n; i++) 50 Scl(a[i]); 51 sort(a+1,a+1+n); 52 LL tmp=0; 53 For_(i,1,n-1)//注意这两个for循环的先后顺序 54 tmp+=a[i]*(n-i); 55 For_(i,1,n) 56 a[i]+=a[i-1];//用来计算每隔k的x次方堆石子被合并的次数是相同的，即(a[m]-a[m-k])*cnt， 57 int q; 58 Sci(q); 59 while(q--) 60 { 61 LL ans=0; 62 LL k; 63 Scl(k); 64 int t=k; 65 LL cnt=1,m=n-1; 66 if(k!=1) 67 { 68 while(m>=k)//当k大于等于n时，不执行，直接执行 ans+=cnt*a[m];，即最小代价是前n-1堆石子个数和，即1*a[m]. 69 { 70 ans+=(a[m]-a[m-k])*cnt; 71 cnt++; 72 m-=k; 73 k=k*t;//k的变化是k k^2 k^3 k^4...每次乘以最初的k的大小，刚开始写成k*=k，wa一下午，我太难了QAQ 74 } 75 ans+=cnt*a[m]; 76 } 77 else 78 ans=tmp; 79 printf("%I64d ",ans);//还有这个谜之输出。 80 } 81 return 0; 82 }
嗯，本来不是难题，硬是用了我一天的时间，真是。。。。。。多个地方都有出过问题。唉。