【解题报告】Examination

Examination

本题解借鉴了这位dalao的思路

看上去这题没人交题解，那我就来一发吧(弥天大雾

传送门

题意

题目已经很简洁力

分析一下

一开始就不满足要求的话是肯定要交换的，我们用大根堆 A，B 分别存储一开始就不满足要求的 \(a_i,b_i\)

而一开始就满足要求的 \(a_i,b_i\)，我们用一个大根堆 q（这里要按照 \(a_i\) 来排）存起来，然后进行交换

考虑如何交换

对于一开始就不满足的人，其内部可以自己解决的话，一定会自己解决（贪心的想），即对于当前的 \(top_B\) 如果 A 内最大的 \(a_i\)（即 \(top_A\) ）大于它，我们就可以直接把这两个人交换，即把当前这个人的 \(a_i,b_i\) 变成 \(top_A,top_B\) 即可

如果无法内部解决，说明我们需要原本合法的人的帮助，我们肯定是要用 \(a_i\) 更大的人才能帮助他的，所以我们之前使用大根堆存合法的人。贪心的想，我们在保证 \(a_i\) 大于 \(top_B\) 的同时，也要使 \(b_i\) 尽量小，因此我们可以使用小根堆 not_B 将所有满足 \(a_i\) 大于 \(top_B\) 的人的 \(b_i\) 存下来，选一个 \(b_i\) 最小的进行交换即可（如果此时 not_B 为空，说明没人能帮 \(top_B\)，即无解）

AC code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define pii pair<int,int>

using namespace std;

const int maxn=3e5+5;

inline int read()
{
   int w=0,f=1;
   char ch=getchar();
   while(ch<'0' || ch>'9')
   {
   	if(ch=='-') f=-1;
   	ch=getchar();
   }
   while(ch>='0' && ch<='9')
   {
   	w=(w<<3)+(w<<1)+(ch^48);
   	ch=getchar();
   }
   return w*f;
}

int n,x,y,ans;
priority_queue<pii,vector<pii>,less<pii> > q;
priority_queue<int,vector<int>,less<int> > A,B; 
priority_queue<int,vector<int>,greater<int> > not_B;

int main()
{
   n=read();

   for(int i=1;i<=n;i++)
   {
   	x=read(),y=read();
   	if(x<y) A.push(x),B.push(y);
   	else q.push(make_pair(x,y)),ans++;
   }
   
   while(!B.empty())
   {
   	int k=B.top();B.pop();
   	
   	if(!A.empty() && A.top()>=k)
   	{
   		A.pop();continue;
   	}
   	
   	while(!q.empty() && q.top().first>=k)
   	{
   		not_B.push(q.top().second);q.pop();
   	}
   	
   	if(not_B.empty()) cout<<-1,exit(0);
   	
   	ans--,B.push(not_B.top()),not_B.pop();
   }
   
   cout<<ans;
   
   return 0;
}