ARC147E Examination

题目大意

给定$A_i,B_i,i\in [1,n]$
每次操作可以交换$A_i,A_j$
要求操作后使得，$\forall i\in [1,n],A_i\ge B_i$，问操作的最少元素个数
$$n\le 300000$$

题解

相当于我们要钦定一个最小的集合$S$，将$S$中的元素重排，使得$S$中的元素全部满足，并且$S$外的元素本来必须满足条件
原本不满足的元素必定要在$S$中，要将最少的合法的元素加入$S$，使得$S$重排后合法
判断$S$是否有解的充要条件为，将$S$中的$A,B$从小到大排序后，$\forall i\in S,A_i\ge B_i$
发现这个条件并不好用
转化一下条件，设$cn{t}_t={\sum }_{i\in S}[B_i\le t]-[A_i\le t]$，充要条件为$\forall t\in N,cn{t}_t\ge 0$
这样每次找到一个最小的$t$使得$cn{t}_t<0$，然后从合法的元素中，为使$cn{t}_t\ge 0$，我们要挑选一个满足$B_i\le t,A_i>t$，显然贪心地选$A_i$最大的会比较优，如果找不到这样的元素，则无解
时间复杂度为$O(n\log n)$

$\text{code}$

#include
#include
#include
using namespace std;
struct node
{
	int x,k;
};
bool operator < (node a,node b)
{
	return a.x>b.x||(a.x==b.x&&a.k<b.k);
}
priority_queue<node> q;
priority_queue<int> h;
const int N=3e5+100;
int n,m,ans;
struct Node
{
	int l,r;
}p[N+10];
bool cmp(Node a,Node b){return a.l<b.l;}
int main()
{
	scanf("%d",&n);
	for(int i=1,a,b;i<=n;i++)
	{
		scanf("%d %d",&a,&b);
		if(a<b) ans++,q.push((node){a,-1}),q.push((node){b,1});
		else p[++m]=(Node){b,a};
	}
	sort(p+1,p+1+m,cmp);
	int res=0;
	for(int x,j=1;!q.empty();)
	{
		x=q.top().x,res+=q.top().k,q.pop();
		while(j<=m&&p[j].l<=x) h.push(p[j].r),j++;
		if(res<0)
		{
			if(h.empty())
			{
				printf("-1");
				return 0;
			}
			int tmp=h.top();h.pop();
			if(tmp<=x)
			{
				printf("-1");
				return 0;
			}
			ans++,res++,q.push((node){tmp,-1});
		}
	}
	printf("%d",n-ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55