题解：P7990 [USACO21DEC] Closest Cow Wins S

Luojt95 · 2025-08-04 16:04:56 · 题解

题目传送门。

思路

这是一道贪心题，需要计算子区间的最大收益。

在两头对方的牛之间，可以最多放 2 头牛。因为再多就不必要了。

• 不放牛：这两头对方的牛之间的草地不要。
• 放 1 头牛：情况较为复杂，设左右对方的牛坐标为 l 和 r ，我方牛坐标为 k ，则 (\frac{l+k}{2},\frac{r+k}{2}) 中的草地归我方所有，注意距离双方相同的草地归属对方。
• 放 2 头牛： 这两头对方的牛之间的草地全要。

此时会产生一个小问题，第 1 头对方的牛之前的草地和第 m 头对方的牛之后的草地无法维护，所以需要在代码实现上添加第 0 头牛和第 m+1 头牛分别在坐标 -\inf 和 \inf ，或直接特殊处理，以确保它们不会影响我方牛占领草地的情况。

代码实现

我们可以用一个滑动窗口来维护整个区间的收益，从左到右枚举一头牛的收益并取最大值，详见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int k,m,n,f[N];
int p,en=2,e=2,g[N],q[N];
struct node{
    int p,t;
    bool operator<(const node&b)const{
        return p<b.p;
    }
}a[N];
signed main()
{
    cin>>k>>m>>n;
    for(int i=0;i<k;i++) cin>>a[i].p>>a[i].t;
    for(int i=1;i<=m;i++) cin>>f[i];
    sort(a,a+k); 
    sort(f+1,f+m+1); //该题不保证输入升序，所以要排序 
    while(p<k&&a[p].p<f[1]) g[0]+=a[p++].t; // 特判第一头牛 
    for(int i=1;i<m;i++)
    {
        int l=p,hh=0,tt=0,ans=0,t=0,mx=0;
        while(p<k&&a[p].p<=f[i+1]) p++;
        for(int j=l;j<p;j++)
        {
            q[hh++]=j;
            ans+=a[j].t;
            t+=a[j].t;
            while(hh!=tt&&(a[j].p-a[q[tt]].p)*2>=f[i+1]-f[i]) ans-=a[q[tt++]].t;
            mx=max(ans,mx); //取各个窗口收益的最大值
        }
        g[e++]=mx;
        g[e++]=t-mx; //存储可能的答案收益 
    }
    while(p<k) g[e]+=a[p++].t; //特判最后的牛 
    e++;
    sort(g,g+e);
    int ans=0;
    for(int i=1;i<=n;i++) ans+=g[--e]; //接收最大的 n 份收益 
    cout<<ans;
    return 0;
}