Codeforces Round #140 (Div. 1) B. Naughty Stone Piles

本文主要是介绍Codeforces Round #140 (Div. 1) B. Naughty Stone Piles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题目链接：http://codeforces.com/problemset/problem/226/B

B. Naughty Stone Piles

There are  n piles of stones of sizes  a1,  a2, ...,  a n lying on the table in front of you.

During one move you can take one pile and add it to the other. As you add pile i to pile j, the size of pile j increases by the current size of pile i, and pile i stops existing. The cost of the adding operation equals the size of the added pile.

Your task is to determine the minimum cost at which you can gather all stones in one pile.

To add some challenge, the stone piles built up conspiracy and decided that each pile will let you add to it not more than k times (after that it can only be added to another pile).

Moreover, the piles decided to puzzle you completely and told you q variants (not necessarily distinct) of what k might equal.

Your task is to find the minimum cost for each of q variants.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of stone piles. The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 109) — the initial sizes of the stone piles.

The third line contains integer q (1 ≤ q ≤ 105) — the number of queries. The last line contains q space-separated integers k1, k2, ..., kq(1 ≤ ki ≤ 105) — the values of number k for distinct queries. Note that numbers ki can repeat.

Output

Print q whitespace-separated integers — the answers to the queries in the order, in which the queries are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64dspecifier.

Examples

input

Copy

5
2 3 4 1 1
2
2 3

output

Copy

9 8 

Note

In the first sample one way to get the optimal answer goes like this: we add in turns the 4-th and the 5-th piles to the 2-nd one; then we add the 1-st pile to the 3-rd one; we add the 2-nd pile to the 3-rd one. The first two operations cost 1 each; the third one costs 2, the fourth one costs 5 (the size of the 2-nd pile after the first two operations is not 3, it already is 5).

In the second sample you can add the 2-nd pile to the 3-rd one (the operations costs 3); then the 1-st one to the 3-th one (the cost is 2); then the 5-th one to the 4-th one (the costs is 1); and at last, the 4-th one to the 3-rd one (the cost is 2).

题目大意：

有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。

         很好理解，每次可以合并的堆的个数增加了，被合并的堆数也在增加。所以排序后，从大到小贪心即可。同时记录答案。

         注意当cnt*=k时可能会爆long long

        注意要记忆化，k可能相等

 This is the code：

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x3f3f3f3f      //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
const int maxn=100005;
LL a[maxn];
LL K[maxn];
LL sum[maxn];
bool cmp(LL x, LL y)
{return x>y;
}
int main()
{//freopen("D:\\chnegxubianji\\inORout\\in.txt", "r", stdin);//freopen("D:\\chnegxubianji\\inORout\\out.txt", "w", stdout);LL n;scanf("%I64d",&n);for(int i=0;i<n;++i)scanf("%I64d",&a[i]);sort(a,a+n,cmp);sum[0]=0;//最后一个不需要加sum[1]=a[1];for(int i=2;i<n;++i)sum[i]=sum[i-1]+a[i];int q;scanf("%d",&q);while(q--){int k;scanf("%d",&k);if(K[k]){printf("%I64d ",K[k]);continue;}LL val=1;//表示这个要移动几次LL res=0;LL cnt=k;//注意要long longLL top;for(LL i=1; i<n; ){top=min(cnt+i-1,n-1);res+=(sum[top]-sum[i-1])*val;val++;//记录需要和并多少次i+=cnt;cnt*=k;//和并的次数是指数上升的}printf("%I64d ",K[k]=res);}return 0;
}

 

这篇关于Codeforces Round #140 (Div. 1) B. Naughty Stone Piles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---