题意：把奶牛分成3组，只要有两组大于1/2量，用深搜剪枝
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=220; 7 struct node 8 { 9 int key,id; 10 bool operator <(const node &xx)const 11 { 12 return key>xx.key; 13 } 14 }data[maxn]; 15 16 bool cmp(const node &p,const node &q) 17 { 18 return p.key<q.key; 19 } 20 int sum[maxn],n; 21 bool use[maxn],flag; 22 void dfs(int t,int ret,int ans) 23 { 24 if(flag) return ; 25 if(ret==n) 26 { 27 if(ans>n*500&&sum[n+n]-ans>n*500) 28 { 29 for(int i=1;i<=n+n;i++) 30 if(use[i]) 31 printf("%d ",data[i].id); 32 for(int i=1;i<=n+n;i++) 33 if(!use[i]) 34 printf("%d ",data[i].id); 35 flag=true; 36 } 37 return ; 38 } 39 if(ans+sum[t]-sum[t-(n-ret)]<=n*500) return ; 40 if(sum[n+n]-(ans+sum[n-ret])<=n*500) return ; 41 for(int i=t;i>=n-ret;i--) 42 { 43 use[i]=1; 44 dfs(i-1,ret+1,ans+data[i].key); 45 use[i]=0; 46 } 47 } 48 49 int main() 50 { 51 scanf("%d",&n); 52 for(int i=1;i<=n*3;i++) 53 { 54 scanf("%d",&data[i].key); 55 data[i].id=i; 56 } 57 sort(data+1,data+1+n*3); 58 sort(data+1,data+1+n+n,cmp); 59 sum[0]=0; 60 for(int i=1;i<=n+n;i++) 61 sum[i]=sum[i-1]+data[i].key; 62 flag=0; 63 memset(use,0,sizeof(use)); 64 dfs(n+n,0,0); 65 for(int i=n+n+1;i<=n*3;i++) 66 printf("%d ",data[i].id); 67 return 0; 68 }