【題目鏈接】Circus
【題目分析】理解題意以后發現并沒有什么思路,沒有什么算法能用,這個時候就應該想到計算機解題的本質——暴力求解。相應的就要想到剪枝的條件,肯定不能盲目的暴力求解。
總共有四種人:00,01,10,11,分別統計出數目c1,c2,c3,c4,設第一個團體a1,a2,a3,a4,按照a3和a4進行暴力,相應的可以求出b4,b2,a2,a1,分別判斷是否合理,一旦合理直接輸出
代碼:
//借鑒大佬的代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;const int MAXN=6000;
char a[MAXN],c[MAXN];
int n;
int cnt[10][10];int main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);scanf("%d",&n);scanf("%s%s",c,a);memset(cnt,0,sizeof(cnt));for(int i=0;i<n;i++){cnt[c[i]-'0'][a[i]-'0']++;}int a1,a2,a3,a4;int b1,b2,b3,b4;int flag=0;for(a4=0;a4<=cnt[1][1];a4++){for(a3=0;a3<=cnt[1][0];a3++){b4=cnt[1][1]-a4;//b3=cnt[1][0]-a3;b2=a3+a4-b4;if(b2<0 || b2>cnt[0][1]) continue;a2=cnt[0][1]-b2;a1=n/2-a4-a3-a2;if(a1<0 || a1>cnt[0][0]) continue;flag=1;break;}if(flag==1) //忘記在這里退出循環一直wa。。。。break;}if(!flag){printf("-1");return 0;}for(int i=0;i<n;i++){if(a1 && c[i]=='0' && a[i]=='0') printf("%d ",i+1),a1--;if(a2 && c[i]=='0' && a[i]=='1') printf("%d ",i+1),a2--;if(a3 && c[i]=='1' && a[i]=='0') printf("%d ",i+1),a3--;if(a4 && c[i]=='1' && a[i]=='1') printf("%d ",i+1),a4--;}return 0;
}