「NOIP模拟赛」买汽水
「问题描述」
暑期集训一共N天，大家都辛苦了，Symbol准备给大家买汽水，但是钱只有M。
每天买汽水的花销都是不固定的，如果不够钱，买到的汽水不够大家一起喝，那样子不太好对不对？所以我们要买的话，就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销，请问我们一共最多能够花掉Symbol多少钱呢？
暑假最多不超过40天，Symbol给大家花的钱最多有一亿。
「输入」
输入第一行有两个整数N，M。 1<=N<=40，0<=M<=100000000。
接下来一行有N个数，表示某一天的汽水花销。每天汽水的花销p<=100000000。
「输出」
输出一个整数，表示我们能够花掉Symbol多少钱。
「输入输出样例一」
| drink.in | drink.out |
| 3 101 2 3 | 6 |
「输入输出样例二」
| drink.in | drink.out |
| 4 104 3 5 11 | 9 |
「数据描述」
对于10%的数据，N<=10。
对于30%的数据，N<=20。
对于60%的数据，N<=30。
对于100%的数据，N<=40。
题解
折半搜索，一半放进平衡树，另一半找M-x的前驱后继更新答案
当然排序后二分也是可以的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> #define inf 100000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,m,tot,ans; int a[45]; set<int> q; void dfs(int x,int sum) { if(sum>m)return; if(x==tot) { if(!flag)q.insert(sum); else { set<int>::iterator t=q.lower_bound(m-sum); if(t!=q.end()&&*t+sum<=m)ans=max(*t+sum,ans); if(t!=q.begin()) { --t; if(*t+sum<=m)ans=max(*t+sum,ans); } } return; } dfs(x+1,sum); dfs(x+1,sum+a[x]); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); flag=0;tot=n/2+1; dfs(1,0); flag=1;tot=n+1; dfs(n/2+1,0); printf("%dn",ans); return 0; } |
Subscribe
计数器 9856404
OI 课件=>
OI 课件=>