1. 买汽水
【问题描述】
暑期集训一共N天，大家都辛苦了，Symbol准备给大家买汽水，但是钱只有M。
每天买汽水的花销都是不固定的，如果不够钱，买到的汽水不够大家一起喝，那样子不太好对不对？所以我们要买的话，就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销，请问我们一共最多能够花掉Symbol多少钱呢？
暑假最多不超过40天，Symbol给大家花的钱最多有一亿。
【输入】
输入第一行有两个整数N，M。 1<=N<=40，0<=M<=100000000。
接下来一行有N个数，表示某一天的汽水花销。每天汽水的花销p<=100000000。
【输出】
输出一个整数，表示我们能够花掉Symbol多少钱。
【输入输出样例一】
|
drink.in |
drink.out |
|
3 10 1 2 3 |
6 |
【输入输出样例二】
|
drink.in |
drink.out |
|
4 10 4 3 5 11 |
9 |
【数据描述】
对于10%的数据，N<=10。
对于30%的数据，N<=20。
对于60%的数据，N<=30。
对于100%的数据，N<=40。
首先把前n/2个和后n-n/2个分开，这样两部分的大小基本上是一样大的
然后前面的直接暴力算出所有解，再算后20个的时候暴力完只要二分第一个小于m-tot的值更新答案就好了
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<deque> 9 #include<set> 10 #include<map> 11 #include<ctime> 12 #define LL long long 13 #define inf 0x7ffffff 14 #define pa pair<int,int> 15 #define pi 3.1415926535897932384626433832795028841971 16 #define mod 1000007 17 using namespace std; 18 struct hashing{int next,v;}hash[2000010]; 19 bool operator < (const hashing &a,const hashing &b){return a.v<b.v;} 20 int head[mod]; 21 int n,m,tot,cnt,ans; 22 int a[100]; 23 inline bool fnd(int u) 24 { 25 int s=u%mod; 26 for (int i=head[s];i;i=hash[i].next) 27 if (hash[i].v==u)return 1; 28 return 0; 29 } 30 inline void insert(int u) 31 { 32 int s=u%mod; 33 hash[++cnt].v=u; 34 hash[cnt].next=head[s]; 35 head[s]=cnt; 36 } 37 inline int bsearch(int x) 38 { 39 int l=1,r=cnt,s=0; 40 while (l<=r) 41 { 42 int mid=(l+r)>>1; 43 if (hash[mid].v<=x){s=hash[mid].v;l=mid+1;} 44 else r=mid-1; 45 } 46 return s; 47 } 48 int main() 49 { 50 freopen("drink.in","r",stdin); 51 freopen("drink.out","w",stdout); 52 scanf("%d%d",&n,&m); 53 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 54 while (a[n]>m)n--; 55 if (n==0) 56 { 57 printf("0"); 58 return 0; 59 } 60 sort(a+1,a+n+1,greater<int>()); 61 sort(a+1,a+(n/2)+1); 62 sort(a+(n/2)+2,a+n+1); 63 for (int i=0;i<1<<(n/2);i++) 64 { 65 tot=0; 66 for (int j=1;j<=n/2;j++) 67 if (i & (1<<(j-1))) 68 { 69 tot+=a[j]; 70 if(tot>m)break; 71 } 72 if (tot>m)continue; 73 if(fnd(tot))continue; 74 insert(tot); 75 } 76 sort(hash+1,hash+cnt+1); 77 for (int i=0;i<=1<<(n-n/2);i++) 78 { 79 tot=0; 80 for (int j=1;j<=n-n/2;j++) 81 if (i & (1<<(j-1))) 82 { 83 tot+=a[j+n/2]; 84 if (tot>m)break; 85 } 86 if (tot>m)continue; 87 int find=bsearch(m-tot); 88 ans=max(ans,find+tot); 89 } 90 printf("%d ",ans); 91 return 0; 92 }