Closest Cow Wins (USACO Silver 2021 December)

每两个相邻的N牛（左边 $f_i$ ，右边 $f_{i+1}$ ）之间，我们都有两个可选的策略：

如果放两头牛，一定可以吃掉所有草，分别放在 $f_i$ 的紧右侧，和 $f_j$ 的紧左侧。这样的总分计为two[i]。
如果放一头牛，则可以以滑动一个有 $ceil(\frac{f_{i+1}-f_i}{2})$ 个连续整数的窗口来计算得分。把最佳分计为one[i]。

第一头N牛之前，和最后一头N牛之后的所有草，都是可以用一头牛全部吃掉的。也加到one[]里面。

然后就是greedy地看，从one[i]和two[i]-one[i]合并的数组中选择最大的n个数来得到后的答案。这个正确的原因如下：

two[i]-one[i]相当地于是把一个区间从一个牛升级到两个牛
我们容易看出two[i] <= 2*one[i]
所以，如果two[i]-one[i]被选中，则one[i]一定也已经被选中，所以这个“升级”的逻辑是对的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int k,m,n;
struct G {
    int p, t;
};
G g[200005];
int nh[200005];
ll one[200005];
ll two[200005];
ll first, last;
 
ll all[400005];
 
bool gcmp(G &a, G &b) {return a.p < b.p;}
 
ll ans;
 
int main() {
    scanf("%d %d %d", &k, &m, &n);
    for (int i = 0; i < k; i++)
        scanf("%d %d", &g[i].p, &g[i].t);
    sort(g, g+k, gcmp);
    for (int i = 0; i < m; i++)
        scanf("%d", &nh[i]);
    sort(nh, nh+m);
 
    // before first nh and after last nh
    int t = 0, i = 0;
    for (; i < k && g[i].p < nh[0]; i++)
        t += g[i].t;
    if (i > 0)
        first = t;
    t = 0; i = k-1;
    for (; i >= 0 && g[i].p > nh[m-1]; i--)
        t += g[i].t;
    if (i < k-1)
        last = t;
 
    int l = 0;      // grass
    for (i = 0; i < m-1; i++) {       // nh
        while (l < k && g[l].p < nh[i])     // find a grass
            l++;
        while (i < m && g[l].p > nh[i+1])   // find the matching nhoj cow to its left
            i++;
        if (i >= m-1)                       // we are past the last nhoj cow
            break;
        for (int r = l; r < k && g[r].p < nh[i+1]; r++)
            two[i] += g[r].t;
        
        // slide window to calc two[i]
        int r = l;
        int w = (nh[i+1] - nh[i] + 1) / 2;
 
        ll t = 0;
        while (l < k && g[l].p < nh[i+1]) {
            while (r < k && g[r].p < nh[i+1] && g[r].p < g[l].p + w) {
                t += g[r].t;
                r++;
            }
            if (t > one[i])
                one[i] = t;
            t -= g[l].t;
            l++;
        }
    }    
 
    // now greedily take best answers
    for (int i = 0; i < m-1; i++) {
        all[i*2] = one[i];
        all[i*2+1] = two[i] - one[i];
    }
    all[(m-1)*2] = first;
    all[(m-1)*2+1] = last;
    sort (all, all+m*2, greater<ll>());
 
    ll ans = 0;
    for (int i = 0; i < m*2 && i < n; i++)
        ans += all[i];
    printf("%lld", ans);
 
    return 0;
}