洛谷P2094 - 运输

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

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

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

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

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

以下为代码：

#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());
}