Codeforces 1187 E

E. Tree Painting

题目描述

There are $n$ piles of stones of sizes $a_1,a_2,\dots,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 \leq n \leq 10^5$) — the number of stone piles. The second line contains $n$ space-separated integers: $a_1,a_2,\dots,a_n$ ($1 \leq a_i \leq 10^9$) — the initial sizes of the stone piles.

The third line contains integer $q$ ($1 \leq q \leq 10^5$) — the number of queries. The last line contains $q$ space-separated integers $k_1,k_2,\dots,k_q$ ($1 \leq k_i \leq 10^5$) — the values of number $k$ for distinct queries. Note that numbers $k_i$ 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 $\%I64d$ specifier.

Examples

input1

2 3 4 1 1

2 3

output1

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$ 堆石子，每堆分别有 $a_1,a_2,\dots,a_n$ 个石子放在你面前的桌子上。

在每次移动中，你可以选择一堆石子，并把它合并到其他的堆上。如果你把第 $i$ 堆加到第 $j$ 堆上，那么第 $j$ 堆会增加当前第 $i$ 堆拥有的石子数，并且第 $i$ 堆将不会继续存在。这样操作的代价是第 $i$ 堆的石子数。

你的任务是考虑把这些石子合成一堆的最小代价。

为了增加一些难度，我们规定，合并的石头堆最多被合并 $k$ 次（在这之后，你只能把这一堆合并到其他堆上）。

此外，你将会被询问 $q$ 次，每次给你可能相同的 $k$ 。

你的任务是对于这 $q$ 个询问，给出最小花费。

分析

我们首先考虑如果只有一次询问我们怎么做。

假设当前每一堆最多被合并 $k$ 次。

假设当前只有 $k+1$ 堆，我们的做法显然是，排序，把最小的 $k$ 堆合并到最大堆上。

假设当前只有 $k+2$ 堆，那么我们可以得到的是，我们需要合并 $k+1$ 次，所以必然有一堆被合并了两次，除了最大堆之外，其他堆合并了一次。要让代价最小，我们需要让最小堆被合并两次。所以操作是，我们把最小堆合并到除最大堆的某一堆，然后其他堆合并到最大堆。

$\dots$

假设当前有 $k*k + k + 1$ 堆，我们怎么操作呢？

首先我们可以确定的是，需要合并 $kk+k$ 次，因为一堆最多被合并 $k$ 次，所以我们可以得到，这 $kk+k$ 次合并中，必定会有 $k$ 次合并，实际上是将两堆及以上合并到了某一堆中，也即：有 $k*k$ 堆被合并了两次，有 $k$ 堆被合并了一次。所以一个显而易见的贪心策略就出来了。

每次我们倍增 $k$ 挑出这么多堆出来，合并次数增加。为了保证答案最小，显然是，最后合并的是大堆，也就是合并次数最少。

代码

给大佬递上我奇丑无比的代码　(/ω＼)

#include<bits/stdc++.h>
using namespace std;
const int maxm = 1e5+10;
int n, q;
long long a[maxm];
void input() {
	cin>>n;
	for(int i = 0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	reverse(a,a+n);
	for(int i = 1;i<n;i++) a[i] += a[i-1];
}
long long get_ans(int len) {
	long long ans = 0;
	long long rlen = len, cnt = 1;
	for(int i = 1;i<n;) {
		int r = min(n-1ll,i+rlen-1);
		ans += (a[r] - a[i-1])*cnt;
		cnt++;
		i = r+1;
		rlen *= len;
	}
	return ans;
}
long long ans[maxm];
void solve() {
	cin>>q;
	while(q--) {
		int len;
		cin>>len;
		if(ans[len]) cout<<ans[len]<<' ';
		else {
			ans[len] = get_ans(len);
			cout<<ans[len]<<' ';
		}
	}
	cout<<endl;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	input();
	solve();
	return 0;
}