一个物品的价钱为p 运费 s
我们优先购买$⌊\frac{P}{2}⌋+S$ 较小的 也就是说买打完折到手比较便宜的
具体证明暂时不会表达 以后想起来会补充的
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
int n,b;
struct node{
int x,y;
}p[N];
bool cmp(node &a,node &b){//根据 价钱/2+运费 排序
return a.x/2+a.y<b.x/2+b.y;
}
int find(){
bool f=true;//是否有优惠卷
int mx=0;//能买的物品中价钱最贵的
for(int i=0;i<n;i++){
auto t=p[i];
if(b>=t.x+t.y){//能买就买
b-=t.x+t.y;
mx=max(mx,t.x);//记录花费最大的等会把优惠卷用掉
}else if(f){
mx=max(mx,t.x);//找包括这一个 价钱最大的
b+=mx/2;//把优惠卷省下的钱加回来
f=false;//优惠卷没了
i--;//等会重新看这个物品能不能买
}else return i;//优惠卷都用完了 还不能买直接返回就行
}
return n;
}
int main(){
cin>>n>>b;
for(int i=0;i<n;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+n,cmp);//排序序
cout<<find();//定义函数是方便打印 不用break for循环了
return 0;
}