题解：P2519 [HAOI2011] problem a

~~喜提最劣解~~

思路

题目中说到第

i

个人有

a_i

个人成绩更低，

b_i

个人成绩更高，我们设

l_i=a_i+1,r_i=n-b_i

，那么这个人在按成绩排序后所在的可能区间即为

[l_i,r_i]

，当然

l_i>r_i

的情况显然是不合法的。

我们可以用类似差分约束的方法做，对于每一个区间

[l_i,r_i]

，将他视为

[l_i,r_i+1)

（方便转移），然后在点

l_i

与点

r_i+1

之间建一条边，长度为在这个区间的人的数量和区间长度的最小值，最后从点 0 开始跑最长路即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,dp[100010],mx[100010];
struct N{
	int a,b;
}a[100010];
bool cmp(N a,N b){
	if(a.a!=b.a)return a.a<b.a;
	return a.b<b.b;
}
int m;
struct P{
	int l,r,k;
}c[100010];
bool Cmp(P a,P b){
	if(a.r!=b.r)return a.r<b.r;
	return a.l<b.l;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
		int l=a[i].a+1,r=n-a[i].b;
		a[i].a=l;a[i].b=r;
	}
	sort(a+1,a+1+n,cmp);
	P pa={-1,-1,1};
	for(int i=1;i<=n;i++){
		if(a[i].a>a[i].b)continue;
		if(pa.l==-1||pa.l!=a[i].a||pa.r!=a[i].b){
			if(pa.l!=-1)c[++m]=pa;
			pa={a[i].a,a[i].b,1};
		}
		else pa.k++;
	}
	if(pa.l!=-1)c[++m]=pa;
	sort(c+1,c+1+m,Cmp);
	for(int i=1;i<=m;i++){
		int l=1,r=i-1;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(c[mid].r>=c[i].l)r=mid-1;
			else l=mid;
		}
		dp[i]=max(dp[i-1],dp[l]+min(c[i].r-c[i].l+1,c[i].k));
	}
	cout<<n-dp[m];
	return 0;
}

题解：P2519 [HAOI2011] problem a

文章操作

题解：P2519 [HAOI2011] problem a

思路

代码

相关推荐

评论

题解：P2519 [HAOI2011] problem a