B. Odd Swap Sort
https://codeforces.com/contest/1638/problem/B
题目描述
有一个数组A,遍历这个数组,若 a i + a i + 1 a_i+a_{i+1} ai+ai+1 的和为奇数,则交换这两个数的位置 s w a p ( a i , a i + 1 ) swap(a_i, a_{i+1}) swap(ai,ai+1) ,使得最终得到的序列是一个非递减的序列。
输入描述
第一行包含一个 T (1≤t≤105) 表示为测试用例数量
每个测试用例的第一行包含一个整数 n (1≤n≤105) — 数组的长度。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109) — 数组的元素。
输出描述
是否为一个非递减序列:Yes 或 No
样例
#1
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
Yes
No
No
Yes
#2
1
5
2 9 6 2 10
No
提示
解析
这题目其实是可以模拟的,不过复杂度为 O ( n 2 ) O(n^2) O(n2) ,数据量很大,因此必然为 TLE。
我们分析一下,题目说 a i + a i + 1 a_i + a_{i+1} ai+ai+1 的和为奇数时才可以交换位置,那么可知如下信息:
- 要交换两个数字必然是一奇一偶,因为只有这样才可以得到奇数。
- 偶数相连或奇数相连的必然为偶数,因此必然无法交换位置。
上面的第二条信息,既然偶数相连或奇数相连都不可能交换位置,那么如果要保证最终的结果为非递减序列,那么所有的偶数序列和奇数序列都必须是非递减的才行。
例如: [ 1 , 2 , 5 , 4 , 3 , 6 ] [1, 2, 5, 4, 3, 6] [1,2,5,4,3,6] 可以分别得到偶数序列 [ 2 , 4 , 6 ] [2, 4, 6] [2,4,6] 和奇数序列 [ 1 , 5 , 3 ] [1, 5, 3] [1,5,3] ,会发现无论如何交换最终也避免不了 5 和 3。
- 第一次交换: [ 1 , 2 , 4 , 5 , 3 , 6 ] [1, 2, 4, 5, 3, 6] [1,2,4,5,3,6] (5+4=9 为奇数,一奇一偶可以交换)
- 第二次交换: [ 1 , 2 , 4 , 5 , 3 , 6 ] [1, 2, 4, 5, 3, 6] [1,2,4,5,3,6] (5+3=8 为偶数,两个奇数无法交换)
因此我们只需要判断偶数序列和奇数序列是否都是递增的就行。
AC Code
public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));public static void main(String[] args) throws Exception {int T = nextInt();while(T-- != 0) {int n = nextInt();int[] A = new int[n+1];for(int i = 1; i <= n; i++) A[i] = nextInt();int even = 0, odd = 0; // 偶数和奇数boolean flag = true; // 默认最终是递增序列for(int i = 1; i <= n; i++) {if(A[i] % 2 == 0) { // 偶数序列if(A[i] >= even) even = A[i]; // 是否递增else {flag = false;break;}} else { // 奇数序列if(A[i] >= odd) odd = A[i]; // 是否递增else {flag = false;break;}}}out.println(flag ? "Yes" : "No");}out.flush();}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
}