hdu 3600 Simple Puzzle 判断N 数码是否有解

Simple PuzzleTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 742    Accepted Submission(s): 234


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include <stdio.h> #include <stdlib.h> #define MAXN 1000100 int a[MAXN] = {0}; int tmp[MAXN]; int num; void merge(int left, int middle, int right) { int i, j, k; i = left, j= middle+1, k = 1; while(i<= middle && j <= right) { if(a[j] < a[i]) { tmp[k++] = a[j++]; num+=(middle-i+1); } else { tmp[k++] = a[i++]; } } while(i <= middle) tmp[k++] = a[i++]; while(j <= right) tmp[k++] = a[j++]; for(i = left, k = 1; i<= right; i++, k++) a[i] = tmp[k]; } void merge_sort(int left, int right) { if(left < right) { int middle = (left + right)/2; merge_sort(left, middle); merge_sort(middle+1, right); merge(left, middle, right); } } int main(){ int n,i,j,cnt,k,hang; while( scanf("%d",&n)&&n){ cnt=0; for(i=0;i<n;++i) {for(j=0;j<n;j++){scanf("%d",&k);if(k!=0) a[cnt++]=k;else hang=n-1-i;}}num=0; merge_sort(0,cnt-1); if(n%2==1){ if(num%2==0) printf("YES\n"); else printf("NO\n");}else{ if((num%2==0&&hang%2==0)||(num%2==1&&hang%2==1)) printf("YES\n"); else printf("NO\n");}} return 0; }