题解：CF2060G Bugged Sort

有意思的简单题。

判定能否通过某种操作达到确定状态的题目，我们可以尝试进一步简化操作。显然每一列是

a_i,b_i

或

b_i,a_i

，不妨将列内序与列间序分开考虑。

由于我们可以同时改变列内序和列间序，所以我们考虑如何只改变列间序（列内序）。事实上，对于两列

i,j

，只需要引入第三列

k

，依次交换

(i,k),(k,j),(i,k)

即可只改变列间序。

但是由于每次改变两列的列间序，所以一定只能列间序改变偶数列。

于是问题变成了若干对

(a_i,b_i)

，任意排序，可以进行偶数次内部交换，要求分别

a,b

递增。考虑贪心，先不考虑内部交换偶数次的限制，对于每一对都使

a_i<b_i

，直接看成线段排序，依次枚举即可。如对于线段

(1,b_1)

，若

b_1>2

，则第二条线段一定是

(2,b_2)

，其中

b_2>b_1

，否则无解，以此类推。

考虑内部序，注意到对于线段有交的连通块，第一条线段的内部序定后，后面的实际上都已经确定，所以每次只能同时翻转一个连通块。假设我们已经排序，对于总次数的奇偶性，偶长块不改变，奇长块一定改变，所以要么初始为偶数，要么存在奇长块。

代码比 dp 好写一些。

CPP

#include<bits/stdc++.h>
#define maxn 210005
#define fi first
#define se second
using namespace std;
const int inf=1e9;

int n,id[maxn];
pair<int,int>p[maxn];
inline void solve(){
	int sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&p[i].fi);
	for(int i=1;i<=n;i++) scanf("%d",&p[i].se),id[i]=i;
	for(int i=1;i<=n;i++) if(p[i].fi>p[i].se) swap(p[i].fi,p[i].se),sum^=1;
	sort(id+1,id+n+1,[](int x,int y){return p[x]<p[y];});
	int r=0,cnt=0,fl=0;
	p[id[n+1]=n+1].fi=inf;
	for(int it=1,i=id[it];it<=n+1;it++,i=id[it]){
		if(p[i].fi<=r){
			if(p[i].se<r) return puts("NO"),void();
			r=p[i].se;
			cnt^=1;
			continue;
		}
		if(it!=1) fl|=cnt;
		cnt=1,r=p[i].se;
	}
	puts(sum&&!fl?"NO":"YES");
}
signed main(){
	signed T=1;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

题解：CF2060G Bugged Sort

文章操作

相关推荐

评论

题解：CF2060G Bugged Sort