题解 CF1452E 【Two Editorials】

less than 1 minute read

Published:

贪心+差分

考虑我们先钦定一个人的选择，即确定他选的左端点，然后判断另一个人选某一个点作为左端点的收益，这里的收益是指，当某一个线段在第二个人的选择中比第一个人的选择获得的值大多少，如果小于 $0$，视作 $0$。

为方便理解，我们建立一个坐标系，横坐标为第二个人选的左端点，纵坐标对应其收益。我们会发现，每一条线段会在坐标轴上留下两个斜率分别为 $1$ 和 $-1$ 的收益线段，线段的两端点根据第一个人选择情况以及线段自身决定(注意：这里得分类讨论，分线段长度大于等于 $K$ 和线段长度小于 $K$，同时一些线段在坐标轴上产生的收益线段启动可能为负值，所以我们得将坐标原点向左偏平移，而只有当某地方的真实横坐标大于等于 $1$ 的时候，我们才能取出来更新答案)。

对于这两条斜率为 $1$ 和 $-1$ 的收益线段，我们在横坐标上打 $tag$ 来实现。具体的，我们当前手上拿着的 $tag$ 表示，当前位置的斜率，即当前位置与前一个位置的差值。时间复杂度 $O(n^2)$ 。

#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define gc getchar()
using namespace std;
const int N=4100;
LL read(){
	ll p=0; bool w=0; char ch=gc;
	while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
	while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
	return w?-p:p;
}
int n,m,K,l[N],r[N],nw,ans,tg[N],ad[N];
I get(int l1,int r1,int l2,int r2){	
	return max(0,min(r1,r2)-max(l1,l2)+1);
}
int main(){
	n=read(),m=read(),K=read();
	FOR(i,1,m) l[i]=read(),r[i]=read();
	FOR(i,1,n-K+1){
		memset(tg,0,sizeof(tg));
		nw=0;
		FOR(j,1,m){
			int len=get(i,i+K-1,l[j],r[j]);
			nw+=len;
			if(len==r[j]-l[j]+1) continue;
			if(r[j]-l[j]+1>=K){
				int pos=0;
				pos=n+len+l[j]-K;
				tg[pos+1]+=1;
				pos=n+l[j];
				tg[pos+1]-=1;
				pos=n+r[j]-K+1;
				tg[pos+1]-=1;
				pos=n+r[j]-len+1;
				tg[pos+1]+=1;
			}
			else{
				int pos=0;
				pos=n+len-K+l[j];
				tg[pos+1]+=1;
				pos=n+r[j]-K+1;
				tg[pos+1]-=1;
				pos=n+l[j];
				tg[pos+1]-=1;
				pos=n+r[j]-len+1;
				tg[pos+1]+=1;
			}
			
		}
		int tmp=0,us=0;
		FOR(j,1,2*n-K+1){
			us+=tg[j];
			tmp+=us;
			if(j>n) ans=max(ans,nw+tmp);
		}
	}
	cout<<ans;
	
	return 0;
}

You May Also Enjoy