- 由于对价格高的物品使用优惠券一定不劣于对价格低的物品使用,因此考虑优惠券只对价格最高的a+b个物品使用,一定可以达到最优解。
- 考虑贪心:对于这a+b个物品,先不考虑优惠券的数量限制,对每个物品选择对该物品来说最优的优惠券。
- 此时使用优惠券数量可能与题目要求数量不符合,需要进行调整:如果x类型优惠券使用过多,则把一部分使用x类型优惠券的物品改为使用y类型优惠券;如果y类型优惠券使用过多,则把一部分使用y类型优惠券的物品改为使用x类型优惠券。
- 选择哪些物品调整,又是一个贪心:不妨设x类型优惠券使用过多,把所有在第2步中使用x类型的物品全部拿出来,把它们按照改变优惠券类型带来的价格增量排序(即使用y类型的价格减去使用x类型的价格),优先选择增量较小的物品改变优惠券类型即可,直到优惠券数量符合题目要求。
- 时间复杂度
。
#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=3e5+5;
int n,m,a,b,p[N],x,y,tot=0;
double p1[N],p2[N],c[N];
inline int red(){
int data=0;bool w=0;char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
if(ch=='-') w=1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return w?-data:data;
}
int cmp(double x,double y){
return x>y;
}
void solve(){
n=red();a=red();b=red();
x=red();y=red();
for(int i=1;i<=n;i++){
p[i]=red();
}
sort(p+1,p+n+1);
for(int i=1;i<=n;i++){
p1[i]=p[i]-p[i]*x*0.01;
p2[i]=p[i]-max(0,p[i]-y);
}
int cnta=0,cntb=0;
double sum=0,res=0;
for(int i=1;i<=n;i++)
sum+=p[i];
for(int i=n-a-b+1;i<=n;i++){
if(p1[i]>p2[i])res+=p1[i],cnta++;
else res+=p2[i],cntb++;
}
tot=0;
if(cnta>=a){
for(int i=n-a-b+1;i<=n;i++)
if(p1[i]>p2[i])c[++tot]=(p2[i]-p1[i]);
sort(c+1,c+tot+1,cmp);
for(int i=1;i<=tot;i++){
double x=c[i];
if(cnta>a){
res+=x;
cnta--;
}else break;
}
}else{
for(int i=n-a-b+1;i<=n;i++)
if(p1[i]<=p2[i])c[++tot]=(p1[i]-p2[i]);
sort(c+1,c+tot+1,cmp);
for(int i=1;i<=tot;i++){
double x=c[i];
if(cntb>b){
res+=x;
cntb--;
}else break;
}
}
printf("%.8f\n",sum-res);
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int T=red();
while(T--)solve();
return 0;
}