題意

輸入n
再輸入n個數為1~n的一種排列
再輸入n-1個1或0，1表示該元素可以和后面的元素進行交換，0表示不能和后面的元素進行交換
讓我們判斷這個數組能否經過交換得到一個遞增序列

分析

我們發現連續的1的范圍內再加上后面一個0 此區間內任意一個元素是可以通過向后交換去到任意位置的
因為連續的1表示區間內所有元素不僅可以向后交換，也可以說是后一個元素可以向前交換。然而0前面的元素卻不能交換到0后面 所以每個小范圍獨立 只要把所有那些連續的1+后一個0 符合條件的范圍內全部排序 之后的序列是個遞增序列 即滿足
否 則不滿足

code

package main;import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class Main{public static void main(String [] args){int n;Scanner sc = new Scanner(System.in);int[] a = new int[200010];int[] bok = new int[200010];int[] pos = new int[200010];n = sc.nextInt();for(int i=1;i<=n;i++){a[i] = sc.nextInt();}int tmp = 0,s=-1,e=-1;String line = sc.next();for(int i=0;i<line.length();i++){tmp = line.charAt(i)-'0';if(s==-1&&tmp==1)s=i;else if(tmp==0&&s!=-1){e=i+1;Arrays.sort(a,s+1,e+1);s=-1;e=-1;}}if(tmp==1&&s!=-1)Arrays.sort(a,s+1,n+1);int i;for(i=1;i<=n;i++)if(a[i]!=i){System.out.println("NO");break;}if(i==n+1)System.out.println("YES");} }

總結

以上是生活随笔為你收集整理的Codeforce - 920C- Swap Adjacent Elements 排序|思维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。