题解：P7990 [USACO21DEC] Closest Cow Wins S / ARIS0_0 - 1

· · 题解

前言

很坑的题，题目中下标没有排序。

感觉其实是下位蓝（？

思路

考虑到两头奶牛即可占领 Farmer Nhoj 的两头相邻奶牛之间的所有草地，接下来考虑一头奶牛的贡献。

设当前考虑的是 Farmer Nhoj 的两头处于 x 和 y 的奶牛之间的所有草地，其中 x < y 且 x \sim y 中没有别的 Farmer Nhoj 的奶牛。

不难发现，一头处于 x < pos < y 的 Farmer John 奶牛，可以往左占领小于 \frac{pos-x}{2}，往右占领小于 \frac{y-pos}{2}。

于是如果两片在 x 到 y 之间（不包含）的牧场，如果他们之间的距离严格小于 \frac{y-x}{2} 的话，就是可以同时被包含的。

同时注意到牧场贡献为正，所以这一部分可以使用双指针维护。

接下来是贪心部分。

这里的贪心策略是我们现将所有只放一头奶牛的代价压入大根堆中，然后每次取出队首，如果队首是取一头奶牛的贡献，则将取两头奶牛的贡献减去取一头奶牛的贡献压入大根堆中。

但是这个贪心的正确性是需要证明的，设一头奶牛的价值是 val_1，两头奶牛的价值是 val_2，这个贪心的正确性取决于 val_1 和 val_2-val_1 的大小关系。

至于为什么 val_1 \ge val_2-val_1 这个贪心才是正确的就不多赘述，这里只证明为什么 val_1 \ge val_2-val_1。

设当前 Farmer Nhoj 的两头奶牛坐标为 x 和 y，其中 x < y。首先，我们考虑 (x, x + \frac{x + y}{2}) 和 (y - \frac{x + y}{2}, y) 这两个区间。

它们的长度都是小于 \frac{y-x}{2} 的，且我们有 x + \frac{x + y}{2} = y - \frac{x + y}{2}，也就是说，我们有左边的草场价值之和和右边的草场价值之和等于 sum。

又因为 val_1 \ge \max \{ lsum, rsum \} \ge \frac{sum}{2}，其中 lsum 和 rsum 分别表示左右半边草场的价值之和。

而我们有 val_2 = sum，于是 val_1 \ge \frac{val_2}{2}，也就是说，2val_1 \ge val_2，val_1 \ge val_2 - val_1。

证毕。

code

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

#define int long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 2e5 + 5;

namespace ARIS0_0{
    int k, m, n, f[N];
    int p[N], t[N], pre[N], val[N][2];
    pii a[N];
    priority_queue <piii> q;

    void init(){
    }
    void solve(){
        cin >> k >> m >> n;
        for (int i = 1; i <= k; i ++ ) cin >> a[i].fi >> a[i].se;
        for (int i = 1; i <= m; i ++ ) cin >> f[i];
        sort(f + 1, f + m + 1);
        sort(a + 1, a + k + 1);
        for (int i = 1; i <= k; i ++ ) p[i] = a[i].fi, t[i] = a[i].se, pre[i] = pre[i - 1] + t[i];

        for (int i = 1; i <= k; i ++ )
            if (p[i] < f[1])
                val[0][0] += t[i], val[0][1] += t[i];
        q.push({{val[0][0], 0}, 0});
        for (int i = 1, j = 1; i < m; i ++ ){
            while (j <= k && p[j] <= f[i]) j ++;
            if (j > k) break;

            int lt = j, rt = j;
            while (rt <= k && p[rt] < f[i + 1]) rt ++;
            rt --; if (lt > rt) continue;
            val[i][1] = pre[rt] - pre[lt - 1];

            int l = lt, r = l;
            while (l <= rt){
                r = max(r, l);
                while (r < rt && 2 * (p[r + 1] - p[l]) < (f[i + 1] - f[i])) r ++;
                int x = pre[r] - pre[l - 1]; val[i][0] = max(val[i][0], x);
                l ++;
            }

            q.push({{val[i][0], 0}, i});
        }
        for (int i = k; i >= 1; i -- )
            if (p[i] > f[m])
                val[m][0] += t[i], val[m][1] += t[i];
        q.push({{val[m][0], 0}, m});

        int ans = 0;
        while (n && q.size()){
            auto f = q.top(); q.pop();
            ans += f.fi.fi;
            if (f.fi.se == 0) q.push({{val[f.se][1] - val[f.se][0], 1}, f.se});
            n --;
        }

        cout << ans << "\n";
    }
    void single(){ init(), solve(); }
    void multi(){ int T; cin >> T; while (T -- ) init(), solve(); }
    void idmulti(){ int id, T; cin >> id >> T; while (T -- ) init(), solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}
// 爱丽丝，最终还是离我们而去了吗。——致ARIS0_0
// 1