比赛链接

D

刚看到这个题目就来了思路，想着用优先队列来做，每次合并最小的两个数，然后把合并好的再添加进优先队列里，不断重复直到只剩一个元素为止，每次合并的重量之和就是答案。问题是只对了65%的数据，仔细想想看，如果总果子的堆数cic_i特别大，最坏能到 101110^{11} 级别，那就会导致内存直接爆炸。果断换一种思路，使用map来做，记录每个重量有多少堆，每次处理最小的重量，因为map天生就是按key来排序的。

注意一个问题：不用mp.size()来做循环变量，这样不好判断是否只剩1个，用tot来记录还剩余几个数，tot等于1时候结束循环。

正确代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

typedef long long ls;
const ls MOD = 1e9 + 7;


void sol(){
	map<ls, ls> mp;
	int n; cin >> n;
	ls tot = 0;
	for (int i = 1; i <= n; i++){
		ls c, w; cin >> c >>w;
		mp[w] += c;
		tot += c;
	}
	ls sum = 0;
	while (tot > 1){
		ls w = mp.begin() -> first;
		ls c = mp.begin() -> second;
		if (c % 2 == 0){
			sum = (sum + 2 * w * c / 2) % MOD;
			mp.erase(w);
			mp[2*w] += c / 2;
			tot = tot - c / 2;
		}
		else{
			if (c > 1){
				sum = (sum + 2 * w * (c - 1) / 2) % MOD;
				mp[2*w] += (c-1)/2;
				tot = tot - (c-1)/2;
			} 
			if (mp.size() > 1){
				mp.erase(w);
				ls w1 = mp.begin() -> first;
				ls c1 = mp.begin() -> second;
				if (c1 >= 1){
					mp[w1 + w]++;
					sum = (sum + w1 + w) % MOD;
					tot -= 1;
					mp[w1]--;
					if (mp[w1] == 0)
						mp.erase(w1);
				}
			}
		}
	}
	cout << sum << endl;
}

int main(){
	sol();	
}