Description
在我们下饭店的时候蛤玮经常负责点菜,今天饭店搞活动,当总价格大于等于X时可以减去Y的优惠,注意如果总价是2X也仅减去一倍Y.蛤玮非常了解菜品也了解大家,他知道每个菜品有一个饱食度,只有菜品饱食度的和不小于K时大家才会吃的开心.请问蛤玮如何点菜才能在让大家吃的开心的前提下花尽量少的钱,输出最后需要付的钱.注意蛤玮是个有追求的人,所以他不会点重复的菜. Input
T(1<=T<=40),表示数据组数. 每组数据第一行n(1<=n<=30),K,X,Y(1<=K,X,Y<=1e9, X>=Y),表示一共有n种菜,X,Y,K如题目中描述. 接下来n行每行两个数ai,bi(1<=ai,bi<=1e8),分别表示第i个菜的价格和饱食度. Output
每组数据输出一个数,表示总价.如果无解则输出”go die”. Sample Input
1 2 2 20 12 10 2 10 2 Sample Output
8 HINT
不可以通过白给店家钱而不买任何东西来得到减价优惠.
题意：由于n很小，我们可以通过中途相遇法来得出所有的可能，在所有可能中寻找最优解。 代码：
#include<stdio.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<math.h> #include<string.h> #define ll long long using namespace std; struct node { ll p,b; bool operator < (const node &t)const{ return b<t.b; } } s1[80000],s2[80000]; ll p[50],b[50]; set<ll> s; set<ll>::iterator it; int main() { int t; ll n; ll k,x,y; scanf("%d",&t); while(t--) { cin>>n>>k>>x>>y; ll sum=0; for(int i=0; i<n; i++) { cin>>p[i]>>b[i]; sum+=b[i]; } if(sum<k) { puts("go die"); continue; } s.clear(); int cnt1=0; int tn=n/2; for(int i=0; i<(1<<tn); i++) { ll tmpp=0,tmpb=0; for(int j=0; j<tn; j++) { if(i&(1<<j)) { tmpp+=p[j]; tmpb+=b[j]; } } s1[cnt1].p=tmpp; s1[cnt1].b=tmpb; cnt1++; } int nt=n-tn; int cnt2=0; for(int i=0; i<(1<<nt); i++) { ll tmpp=0,tmpb=0; for(int j=0; j<nt; j++) { if(i&(1<<j)) { tmpp+=p[j+tn]; tmpb+=b[j+tn]; } } s2[cnt2].p=tmpp; s2[cnt2].b=tmpb; cnt2++; } sort(s1,s1+cnt1); sort(s2,s2+cnt2); int j=cnt2-1; ll ans=10000000000LL; ll ax; for(int i=0; i<cnt1; i++) { ll tmp=max(0LL,k-s1[i].b); while(s2[j].b>=tmp&&j>=0) { s.insert(s2[j].p); j--; } if(s.empty()) continue; ax=s1[i].p; if(ax+(*s.begin())<x) { ans=min(ans,ax+(*s.begin())); ll c=max(0LL,x-ax); it=s.lower_bound(c); if(it==s.end()) continue; ax+=(*it); ax-=y; ans=min(ans,ax); } else ans=min(ans,ax+(*s.begin())-y); } cout<<ans<<endl; } return 0; }