题意：一个序列有一些数是缺失的，长度为n元素为1到n不重样，要求将缺失的数填进去并尽可能让相邻的两个数奇偶性相同，输出最小的相邻奇偶性不同的数对的数目。
思路：维护还可以填多少个奇数和偶数的数目，如果 奇 0...0 奇，类似这种区间，如果里面能填相同性质的数并且填满的话，就优先填这些，然后数目-长度，然后考虑不同性质的区间，类似于 奇 0....0 偶，这种区间对答案的最小贡献为1，且一定可以是1，然后就是判断最左端和最右端，如果够填得下，对答案无贡献，填不下那么多，贡献就是1.
记录一下我的自闭之旅！
AC代码：（只有我能看得懂，手动滑稽！）
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 int n; 6 int a[160],vis[3]; 7 int k,cnt; 8 9 struct node2{ 10 int len; 11 int col; 12 }n2[160]; 13 14 struct node1{ 15 int col,pos; 16 }n1[160]; 17 18 bool cmp(node2 a,node2 b){ 19 return a.len<b.len; 20 } 21 22 void checkn1(){ 23 for(int i=1;i<=k;i++){ 24 cout<<i<<"->"<<n1[i].col<<" "<<n1[i].pos<<endl; 25 } 26 } 27 28 void checkn2(){ 29 cout<<"checkn2\n"; 30 for(int i=1;i<=cnt;i++){ 31 cout<<i<<"->"<<n2[i].col<<" "<<n2[i].len<<endl; 32 } 33 } 34 35 int main() 36 { 37 cin>>n; 38 39 for(int i=1;i<=n;i++){ 40 cin>>a[i]; 41 if(a[i]!=0){ 42 n1[++k].col=a[i]%2; 43 n1[k].pos=i; 44 vis[a[i]%2]++; 45 } 46 } 47 if(n==1){ 48 cout<<0; 49 return 0; 50 } 51 // 52 //checkn1(); 53 int ans=0; 54 for(int i=1;i<=k-1;i++){ 55 if(n1[i].col==n1[i+1].col&& n1[i+1].pos-n1[i].pos-1!=0 ){ 56 n2[++cnt].col=n1[i].col; 57 n2[cnt].len=n1[i+1].pos-n1[i].pos-1; 58 } 59 if(n1[i].col!=n1[i+1].col) ans++; 60 } 61 //checkn2(); 62 sort(n2+1,n2+1+cnt,cmp); 63 int os=n/2-vis[0],js=(n+1)/2-vis[1]; 64 for(int i=1;i<=cnt;i++){ 65 node2 now=n2[i]; 66 if(now.col==1){ 67 if(now.len<=js) 68 js-=now.len; 69 else 70 ans+=2; 71 } 72 else if(now.col==0){ 73 if(now.len<=os) 74 os-=now.len; 75 else 76 ans+=2; 77 } 78 } 79 // cout<<"caonima2 "<<ans<<endl; 80 int tmp; 81 82 if(a[1]==0&&n1[1].col==1&&js<n1[1].pos-1) ans++; 83 if(a[n]==0&&n1[k].col==1&&js<n-n1[k].pos) ans++; 84 85 if(a[1]==0&&n1[1].col==0&&os<n1[1].pos-1) ans++; 86 if(a[n]==0&&n1[k].col==0&&os<n-n1[k].pos) ans++; 87 88 if(k==0||k==1) ans=1; 89 cout<<ans; 90 return 0; 91 }
原文：https://www.cnblogs.com/qq2210446939/p/12158484.html
