题解：CF1223C Save the Nature

Rex01 · 2025-02-06 11:29:31 · 题解

CF1223B 题目传送门

题目大意

总共 q 次询问，每次询问有 n 个数，随后四个数 x,a,y,b，表示 n 个数中的第 a,2a,3a\cdots 个数有 x\% 的贡献，第 b,2b,3b\cdots 个数有 y\% 的贡献。如果数列中的某一个数是 a,b 的公倍数，则它有(x+y)\% 的贡献。求贡献 \geq k 时，最少用多少个数。

解决思路

可以发现选取的数越大，贡献就越大，因此我们可以将数列从大到小排序，并用二分，求出贡献最大值，若 \geq k 则输出，否则输出 -1。可以发现总共有三种情况（按优先级从大到小讨论）：

分别算出三种情况并从大到小分配票即可。

代码展示

#include <iostream>
#include <algorithm>
//拒绝万能头，从我做起
#define ll long long
//不开 long long 见祖宗
using namespace std;

const int N = 2e5 + 10;
ll q, n, p[N], x, a, y, b, k, p1[N];

bool cmp(ll x, ll y)
{//排序函数
    return x > y;
}

bool check(ll m)
{//二分检查函数
    ll sum = 0;
    for(ll i = 1; i <= m; i++)
    {
        p1[i] = 0;
        if(i % a == 0) p1[i] += x;
        if(i % b == 0) p1[i] += y;
    }
    sort(p1 + 1, p1 + m + 1, cmp);//从大到小排序 
    for(ll i = 1; i <= m; i++)
        sum += p[i] * p1[i];
    return sum >= k;
}

int main()
{
    cin >> q;
    while(q--)
    {
        cin >> n;
        for(ll i = 1; i <= n; i++)
        {
            cin >> p[i];
            p[i] /= 100;//除以100方便计算
        }
        sort(p + 1, p + n + 1, cmp);//从大到小排序
        cin >> x >> a >> y >> b >> k;
        ll l = 1, r = n + 1;
        while(l < r)
        {//二分答案
            ll mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(r == n + 1) cout << -1 << endl;
        else cout << r << endl;
    }
    return 0;
}