牛客题解 装进肚子

链接：https://ac.nowcoder.com/acm/problem/14721

来源：牛客网

题解

作者 岛田小雅

这道题刚拿到手，就感觉是个很简单（事实证明并不是很简单）的贪心。虽然我不是很会判断贪心的适用范围，但是我决定相信自己的直觉。

我的第一想法是：分别把巧克力按照早上和晚上的甜度从大到小排列，得到一个数组 \(a\)（白天的巧克力甜度序列）和一个数组 \(b\)（晚上的甜度序列），然后在早上和晚上的巧克力都没吃满的时候，可以从两组的巧克力的最大值里面找最大的那个吃掉，同时在那颗巧克力上标记已经吃掉了。吃掉的巧克力在下次挑选时不可以再被选中。一旦早上的巧克力或者晚上的巧克力吃满了，剩下的就全给没吃满的时刻吃掉。实现使用优先队列模拟。

然后得到一个样例通过率 0% 的 WA。

出了什么问题呢？我突然意识到，如果在取走一个时刻甜度为当前最高的巧克力时，那个巧克力同时也是另一个时刻剩下巧克力里不可取代的较大值，那这个方案就会挂。

比如这个样例：

5 2
6 5 5 6 1
5 0 3 0 0

如果我们按照刚才的策略去选择，得到的方案是白天吃掉编号为 \(1\) 和 \(4\) 的巧克力，晚上吃 \(2\)，\(3\) 和 \(5\)，甜度值总和是 \(15\)。但其实我们白天吃 \(2\)，\(4\)，晚上吃 \(1\)，\(2\) 和 \(5\) 得到的甜度值是 \(19\)，比刚才的方案更优。

也不知道出题人是谁居然每个点都有这种数据（样例通过率 0% 的怨念）。当然，不排除还有别的地方会逻辑错误（但是我看不出来）。

因为懒得去想怎么修改，第二次尝试我直接换了策略。我们决定一块巧克力在什么时候吃，应该取决于这块巧克力在白天和夜晚跟其它巧克力甜度值的差值大小。如果白天的差值比夜晚大，那在白天吃更优，否则应该在晚上吃。

这样我们就可以直接用一个很简单的排序策略来计算出正确的结果啦。

AC 代码

作者 岛田小雅

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+1;
int n, k;
pair<int,int> lst[N];
long long ans;

bool cmp(pair<int,int> x, pair<int,int> y)
{
    return x.first-y.first > x.second-y.second;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> lst[i].first;
    for(int i = 1; i <= n; i++) cin >> lst[i].second;
    sort(lst+1,lst+1+n,cmp);
    for(int i = 1; i <= n; i++)
    {
        if(i<=k) ans += lst[i].first;
        else ans += lst[i].second;
    }
    cout << ans;
    return 0;
}