TIOJ-1861

發表於 更新於 Disqus：

description

給定一長度$n$的序列序列$a$

將一塊大小為$\sum a_i$的人(?)切成$n$份，對應到$a$

將一塊$x$大小切成$a,b$需要成本$x$

求最佳化切法的最小成本

$n\leq 10^5$

$a_i\leq 10^4$

solution

把問題反過來想，可以發現等價於將$n$個數字合併，成本為合併後數字

要讓它最小，可以greedy地每次都將當前兩個最小的合併

sol.1

利用heap維護當前最小
將所有數字都丟進去，每次取最小的兩個出來合併後丟回去
複雜度$\mathcal{O}(nlogn)$

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int n;
	while(cin >> n) {
		priority_queue<int, vector<int>, greater<int>> pq;
		for(int i = 0, a; i < n; i++)
			cin >> a, pq.push(a);
		ll ans = 0;
		for(int i = 0; i < n-1; i++) {
			int a = pq.top(); pq.pop();
			int b = pq.top(); pq.pop();
			ans += a+b;
			pq.push(a+b);
		}
		cout << ans << '\n';
	}

	return 0;
}

sol.2

可以發現到，每次合併後丟回去的數字都會成單調遞增，因此根本不用使用heap
只要用個queue把它們存起來就好，每次就取(排序後原數列前兩個和queue前兩個)四個中最小的兩個出來就好
複雜度 $\mathcal{O}(n+nlogn)$<br/
如果把排序改成radix 複雜度$\mathcal{O}(n)$

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

void radix_sort(vector<int> &arr) {
	vector<vector<int>> digs(10);
	for(int i = 0, cur = 1; i < 5; i++, cur*=10) {
		for(int j = 0; j < arr.size(); j++) {
			digs[arr[j] / cur % 10].push_back(arr[j]);
		}
		for(int j = 0, it = 0; j < 10; j++) {
			for(int &a: digs[j])
				arr[it++] = a;
			digs[j].clear();
		}
	}
}
queue<int> old;
queue<long long> nw;

long long getn() {
	long long tmp;
	if(nw.empty() || (old.size() && old.front() < nw.front()))
		tmp = old.front(), old.pop();
	else
		tmp = nw.front(), nw.pop();
	return tmp;
}

signed main() {
	EmiliaMyWife

	int n;
	while(cin >> n) {
		while(old.size())
			old.pop();
		while(nw.size())
			nw.pop();
		vector<int> arr(n);
		for(int i = 0; i < n; i++)
			cin >> arr[i];

		radix_sort(arr);
		for(int i = 0; i < n; i++)
			old.push(arr[i]);

		long long ans = 0;
		for(int i = 1; i < n; i++)  {
			long long a = getn(), b = getn();
			ans += a+b;
			nw.push(a+b);
		}
		cout << ans << '\n';
	}

	return 0;
}