2019年3月8日比赛（知网是什么）

第一题（对冒泡排序原理的理解）

题意：第一行的输入代表下一行输入的无序数的数的个数，然后下一行，数字与上一行数字对应，若对应为1则该数可以与下一个数交换位置。

根据冒泡排序可知，任何一个无序序列都可以通过相邻元素交换变成有序的。如果当前数字不能交换，则判断它是否等于其下标+1，否则判断找出这一段‘1’的右边界，a对应值为0的地方

如果当前数字不能交换，则判断它是否等于其下标+1,；

#include
#include
#includeusing namespace std;
int n, a[200005];
char str[200005];
int main()
{ cin >> n;memset(str, 0, sizeof(str));for (int i = 0; i < n; i++)cin >> a[i];cin >> str;int i, j;for (i = 0; i < n; i++){ //判断该点能否被交换if (str[i] == '1') //若能交换{ int maxx = 0;					//maxx相当于是某个区域内的最大值，//如果到端点处（即该点对应的数组a的值为0）判断maxx 是否 大于j + 1来判断是否能通过冒泡的方法实现成功排序。//通过不断地更新区域来实现上述过程的重复即可检验。for (j = i; ; j++){ if (a[j] < i + 1){ cout << "NO" << endl;exit(0);}maxx = max(maxx, a[j]);if (str[j] == '0' || str[j] == 0)			//{ if (maxx > j + 1){ cout << "NO" << endl;exit(0);}i = j;break;}}}else if (a[i] != i + 1) //若不能交换并且处的值不为拍好顺序后的值则输出NO{ cout << "NO" << endl;exit(0);}}cout << "YES" << endl;return 0;
}