题解：P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2

将

(A_i,B_i)

看为左部点，

(C_i,D_i)

看为右部点，两个不同部分的点

(A_i,B_i),(C_j,D_j)

之间有一条边权为

[A_i=C_j]

的边，当且仅当

B_i\le D_j

。那么本题就是求最大权二分图匹配。

直接做肯定不行，但是注意到边权只有

0

或

1

，所以考虑贪心。

设从前往后扫左部点扫到了

(A_i,B_i)

，我们贪心地找与

(A_i,B_i)

有边相连，边权为

1

且

D_j

最大的右部点

(C_j,D_j)

。如果连上这条边后，这个二分图还存在完美匹配，那么就选择这条边。

不难发现，对于一个左部点

(A_i,B_i)

，所有满足

j<i

的左部点

(A_j,B_j)

的边集是包含于

(A_i,B_i)

的，所以容易反证出以上的贪心是对的。

接着考虑判完美匹配，直接拿个线段树跑个 Hall 定理即可。

时间复杂度

O(n\log n)

。

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=2e5+5;
int n;
struct node{
	int c,p;
}a[Maxn],b[Maxn];
int c[Maxn];
struct Tree{
	int val,tag;
}t[Maxn<<2];
void build(int x,int l,int r){
	if(l==r)return void(t[x]={c[l]-l,0});
	int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	t[x].val=min(t[x<<1].val,t[x<<1|1].val);
}
inline void add_(int x,int p){
	t[x].tag+=p;t[x].val+=p;
}
inline void spread(int x){
	add_(x<<1,t[x].tag);add_(x<<1|1,t[x].tag);
	t[x].tag=0;
}
void change(int x,int l,int r,int L,int R,int p){
	if(L>R)return;
	if(L<=l&&r<=R)return void(add_(x,p));
	int mid=l+r>>1;spread(x);
	if(mid>=L)change(x<<1,l,mid,L,R,p);
	if(mid<R)change(x<<1|1,mid+1,r,L,R,p);
	t[x].val=min(t[x<<1].val,t[x<<1|1].val);
}
int query(int x,int l,int r,int L,int R){
	if(L>R)return 114;
	if(L<=l&&r<=R)return t[x].val;
	int mid=l+r>>1,res=114;spread(x);
	if(mid>=L)res=query(x<<1,l,mid,L,R);
	if(res<1)return res;
	if(mid<R)return query(x<<1|1,mid+1,r,L,R);
	return 114;
}
set<int>s[Maxn];
int whe[Maxn];
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]={read(),read()};
	for(int i=1;i<=n;i++)b[i]={read(),read()};
	int p=1;
	for(int i=1;i<=n;i++){
		while(p<=n&&b[p].p>=a[i].p)whe[p]=i,p++;
		c[i]=p-1;
	}
	build(1,1,n);
	p=1;int ans=n;
	for(int i=1;i<=n;i++){
		while(p<=n&&b[p].p>=a[i].p)s[b[p].c].insert(p),p++;
		if(s[a[i].c].empty())continue;
		int id=(*s[a[i].c].rbegin());
		if(query(1,1,n,whe[id],i-1)>0){
			ans--;change(1,1,n,whe[id],i-1,-1);
			change(1,1,n,i,i,1000000000);
			s[a[i].c].erase(id);
		}
	}printf("%d\n",ans);
	return 0;
}

题解：P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2

文章操作

相关推荐

评论

题解：P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2