洛谷P2094 - 运输

  被浏览

这道题第一眼像是合并果子,我们考虑贪心。

我们先选择一种贪心策略:每次选当前最大的两个数合并,直到只剩最后一件物品。

接下来我们证明一下为什么这样是对的:

我们先想一想合并果子,那道题的贪心策略与这道题相反,每次选最小的两个数合并。考虑它为什么是对的——我们发现越先选的数对结果的贡献越大,为了使结果尽可能小,肯定是越小的先选越好。

有了这题做基础,我们来考虑这道题。我们发现越先选的数被$k$除的次数也就越多,为了使结果尽可能小,肯定是让越大的数除$k$的次数越多越好,自此,贪心策略证明完毕。

以下为代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
#define gc c = getchar()
int read(){
int x = 0, f = 1; char gc;
for(; !isdigit(c); gc) if(c == '-') f = -1;
for(; isdigit(c); gc) x = x * 10 + c - '0';
return x * f;
}
#undef gc
priority_queue<int>q;
int main(){
int n = read(), k = read();
for(int i = 1; i <= n; i++) q.push(read());
while(q.size() > 1) {
int x = q.top(); q.pop();
int y = q.top(); q.pop();
q.push((x + y) / k);
}
printf("%d", q.top());
}