题解：P7990 [USACO21DEC] Closest Cow Wins S

思路

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

在两头对方的牛之间，可以最多放

2

头牛。因为再多就不必要了。

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

此时会产生一个小问题，第

1

头对方的牛之前的草地和第

m

头对方的牛之后的草地无法维护，所以需要在代码实现上添加第

0

头牛和第

m+1

头牛分别在坐标

-\inf

和

\inf

，或直接特殊处理，以确保它们不会影响我方牛占领草地的情况。

代码实现

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

CPP

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

题解：P7990 [USACO21DEC] Closest Cow Wins S

文章操作

思路

代码实现

相关推荐

评论

题解：P7990 [USACO21DEC] Closest Cow Wins S