Codeforces 1240A. Save the Nature

显然可以二分答案

如果知道卖的票数，那么就能算出有多少 $a$ 倍数但不是 $b$ 倍数的位置，多少 $b$ 倍数但不是 $a$ 倍数的位置，多少既是 $a$ 又是 $b$ 倍数的位置

然后贪心地把每张票分配给那些位置即可

把价格从大到小排序并预处理前缀和就可以 $O(1)$ 求出最大收益了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll 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<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7;
ll Q,n,p[N],X,Y,A,B,K;
ll sum[N];
ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }
bool check(ll p)
{
    ll ab=p/(1ll*A/gcd(A,B)*B),a=p/A-ab,b=p/B-ab;
    return sum[ab]/100*(X+Y)+(sum[ab+a]-sum[ab])/100*X+(sum[ab+a+b]-sum[ab+a])/100*Y>=K;
}
int main()
{
    Q=read();
    while(Q--)
    {
        n=read();
        for(int i=1;i<=n;i++) p[i]=read();
        sort(p+1,p+n+1); reverse(p+1,p+n+1);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+p[i];
        X=read(),A=read();
        Y=read(),B=read();
        if(X<Y) swap(X,Y),swap(A,B);
        K=read();
        ll L=1,R=n,Ans=N;
        while(L<=R)
        {
            int mid=L+R>>1;
            if(check(mid)) Ans=mid,R=mid-1;
            else L=mid+1;
        }
        if(Ans==N) printf("-1\n");
        else printf("%lld\n",Ans);
    }
    return 0;
}

Codeforces 1240A. Save the Nature

推荐阅读