题解：CF1223C Save the Nature

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

。可以发现总共有三种情况（按优先级从大到小讨论）：

$a_i$ 可以被 $a,b$ 的公倍数整除，有 $(x+y)\%$ 的贡献；
$a_i$ 可以被 $a$ 整除，有 $x\%$ 的贡献；
$a_i$ 可以被 $b$ 整除，有 $y\%$ 的贡献。

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

代码展示

CPP

#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;
}

题解：CF1223C Save the Nature

文章操作

CF1223B 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF1223C Save the Nature