| ||||||||||
| 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