Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
都说是随机,来个搜索吧//136K 16MS #include<iostream> #include<algorithm> using namespace std; struct node { int ord; int val; }; node d[200]; int k,n; int up,down,s[130]; bool visit[130]; bool dfs(int b,int num,int sum) { if(num==k) { if(sum>=down&&sum<=up) { int i; for(i=0;i<n;i++) { if(visit[i]) printf("%d\n",d[i].ord); } for(i=0;i<n;i++) { if(!visit[i]) printf("%d\n",d[i].ord); } return true; } return false; } if(sum+s[b]-s[b+k-num]<down||sum+s[n-k+num]>up) return false; for(int i=b;i<n;i++) { visit[i]=true; if(dfs(i+1,num+1,sum+d[i].val)) return true; visit[i]=false; } return false; } bool cmp(const node &x,const node &y) { return x.val>y.val; } int main() { int i; scanf("%d",&k); n=3*k; for(i=0;i<n;i++) { scanf("%d",&d[i].val); d[i].ord=i+1; } sort(d,d+n,cmp); for(i=2*k;i<n;i++) printf("%d\n",d[i].ord); n-=k; for(i=n-1;i>=0;i--) s[i]=s[i+1]+d[i].val; down=500*k+1; up=s[0]-down; dfs(0,0,0); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator