1365B - Trouble Sort

链接:

https://codeforces.com/problemset/problem/1365/B

题意:

给定序列a和b,ai和bi视为一个整体,ai为1到1E5整数,bi为0或1

只能进行将b=0和b=1的数字交换,求能否让序列a有序

解:

如果只有0,或者只有1,那么需要原来的a序列本身有序,直接判断

如果有0有1,直接是yes

因为假设A,B的b为0,还有一个C的b为1

ACB(010)->CAB(100)->BAC(001)->BCA(010)

只要有一个0,所有的1就能做到互换(三步),对于所有0的数字也是一样

实际代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#define csh(a) memset(a,0,sizeof(a))
using namespace std;
const int Size=5E2+25;
int sz[Size];
int px[Size];
bool check(int n)
{
	for(int i=1;i<=n;i++)
	{
		if(sz[i]!=px[i]) return false;
	}
	return true;
}
int main()
{
	int T;
	cin>>T;
	for(int f=1;f<=T;f++)
	{
		csh(sz);csh(px);
		int n;
		cin>>n;
		int book=-1;
		for(int i=1;i<=n;i++)
		{
			cin>>sz[i];
			px[i]=sz[i];
		}
		for(int i=1;i<=n;i++)
		{
			if(i==1)
			{
				cin>>book;
			}
			else
			{
				int temp;cin>>temp;
				if(book==0 && temp==1) book=2;
				if(book==1 && temp==0) book=2;
			}
		}
		//cout<<"Book"<<book<<endl;
		if(book==2) cout<<"Yes"<<endl;
		else
		{
			sort(px+1,px+n+1);
			if(check(n)) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}

限制:

problem/1365/B

上一篇:cook book:12:并发编程


下一篇:2021-10-18 数学建模小结