写在前边:
本题目使用贪心是行不通的,为啥呢?
如果我们优先使用折后的价格进行递增排序,那么在实际购买中并不是以折后价购买的,只有一个是
折后价购买的;那么你会说我用原价格进行递增排序呢,这个也是不行的,例如:
2 10
2 10
10 4
这组数据,如果按照原价进行排序,那么结果为0,这时你会说我进行特判,如果数据量很大,如何特判?
一番折腾这两种贪心思路只能过11/14个数据!
本题目不能直接使用贪心做,可以进行暴力枚举,O(n^2)的时间复杂度,排序后枚举奶牛i使用优惠券,
并记录购买礼物数量的最大值!
代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1100;
typedef long long ll;
struct res{
int a,b;
ll s;
}t[N];
int m[N];
bool cmp(res x,res y){
ll t1=x.a/2+x.b;
ll t2=y.a/2+y.b;
if(x.s==y.s)
{
return t1<t2;
}
return x.s<y.s;
}
int main(){
int n;
int mo;
cin>>n>>mo;
for(int i=0;i<n;i++){
cin>>t[i].a>>t[i].b;
t[i].s=ll(t[i].a+t[i].b);
}
sort(t,t+n,cmp);
ll sum=0;
int ans=0;
int p=0;
/*
for(int i=0;i<n;i++){
cout<<t[i].a<<' '<<t[i].b<<endl;
}
*/
for(int i=0;i<n;i++){
int ss=ans;
ans=0;
sum=0;
int temp=i;
sum+=t[i].a/2+t[i].b;
if(sum>mo){
continue;
}
ans++;
//cout<<"i: "<<i<<" sum: "<<sum<<" ans: "<<ans<<endl;
for(int j=0;j<n;j++){
if(j!=temp){
sum+=t[j].s;
if(sum<=mo){
ans++;
}
}
if(sum>mo){
ans=max(ss,ans);
m[i]=ans;
break;
}
//cout<<"i: "<<i<<" sum: "<<sum<<" ans: "<<ans<<endl;
}
ans=max(ss,ans);
m[i]=ans;
}
sort(m,m+n,greater<int>());
/*
for(int i=0;i<n;i++){
cout<<m[i]<<endl;
}
*/
cout<<m[0]<<endl;
return 0;
}
还有一种O(nlogn)级别的做法是二分,对礼物数量进行二分!