题意：有n（1<=n<=10^5）堆石子，每堆有ai（1<=ai<=10^9）个石子，每次将一堆石子a合并到另一堆b花费为a，求把所有石子合并一起的最小花费。
不过没有那么简单，现在有m（1<=m<=10^5）个询问ki（1<=ki<=10^5），问每堆石子至多被合并ki次，求把所有石子合并在一起的最小花费。
题解：看到数据量显然贪心+乱搞。
首先想ki = 1的情形，不难想到，一堆石子被合并一次，一堆石子被合并一次…一堆石子被合并一次，这显然是让最少的石子去合并别的石子n-1次。
考虑ki = 2，一堆石子被合并二次，二堆石子被合并二次，四堆石子被合并二次…即每次*2。
很好理解，每次可以合并的堆的个数增加了，被合并的堆数也在增加。所以排序后，从大到小贪心即可。
卡在__int64上居然是re，唉还是考虑不周全10^5不会超int，但是10^5 * 10^5就果断超了唉，比赛可惜了…
PS：cf紫了，下场估计要掉rt了…
Sure原创，转载请注明出处。
[cpp]
#include
#include
#include
#include
using namespace std;
const int maxn = 100002;
__int64 stone[maxn],sum[maxn],ans[maxn];
int m,n,q;
bool cmp(__int64 a,__int64 b)
{
return a > b;
}
void read()
{
memset(ans,-1,sizeof(ans));
for(int i=0;i
scanf("%I64d",&stone[i]);
}
sort(stone , stone + n , cmp);
sum[0] = 0LL;
sum[1] = stone[1];
for(int i=2;i
sum[i] = sum[i-1] + stone[i];
}
return;
}
void solve()
scanf("%d",&m);
bool flag = false;
while(m--)
{
if(flag) printf(" ");
scanf("%d",&q);
if(ans[q] != -1)
{
printf("%I64d",ans[q]);
continue;
}
__int64 res = 0;
__int64 cnt = q,val = 1;
for(__int64 i=1;i<1LL * n;)
{
int top;
if(cnt+i-1 > 1LL * (n-1)) top = n-1;
else top = (int)(cnt+i-1);
res += (sum[top] - sum[i-1]) * val;
i += cnt;
val++;
cnt *= 1LL * q;
}
ans[q] = res;
printf("%I64d",res);
flag = true;
}
puts("");
return;
}
int main()
{
while(~scanf("%d",&n))
{
read();
solve();
}
return 0;
}