题解 [CF720A] Closing ceremony

题面

解析

首先贪心地想一想,

一个人我们肯定让她坐得尽量远,

那到底坐到哪里呢?

考虑先让下面的人先坐,

那他们就要尽量把离上面入口远的位置坐掉,

因此把位置按离上面的距离从大到小排序,

再一个个看能否被下面的人坐到.

并且肯定是让刚刚好能坐到这个位置的人坐最好(lower_bound一下).

最后把剩下的位置与上面的人一一判断即可.

code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <set>

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=100005;

struct node{int x,y,dis;}p[N],q[N];

int n,m,k,a[N],b[N],ans=1;

int tot,pp,v[N];

multiset <int> s;

bool cmp1(node a,node b){

	return a.x+a.y!=b.x+b.y? a.x+a.y>b.x+b.y:a.dis>b.dis;

}

bool cmp(node a,node b){

	return a.dis!=b.dis? a.dis>b.dis:a.x+a.y>b.x+b.y;

}

bool cmp2(node a,node b){

	return a.dis>b.dis;

}

signed main(){

	n=read();m=read();

	k=read();

	for(int i=1;i<=k;i++) a[i]=read();

	int tt=read();

	for(int i=1;i<=tt;i++) b[i]=read();

	sort(a+1,a+k+1);

	sort(b+1,b+tt+1);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			p[++pp].x=i;p[pp].y=j;

			p[pp].dis=m+i-j+1;

		}

	sort(p+1,p+pp+1,cmp);

	for(int i=1;i<=k;i++) s.insert(a[i]);

	for(int i=1;i<=pp;i++){

		int d=p[i].x+p[i].y;

		multiset<int>::iterator it=s.lower_bound(d);

		if(it!=s.end()) s.erase(it);

		else q[++tot]=p[i];

	}

	if(!s.empty()){puts("NO");return 0;}

	pp=0;int tp=1;

	for(int i=1;i<=tot;i++) p[++pp]=q[i];

	sort(p+1,p+pp+1,cmp2);

	for(int i=tt;i>=1;i--){

		if(b[i]<p[tp].dis){ans=0;break;}

		tp++;

	}

	puts(ans? "YES":"NO");

	return 0;

}