|
20鱼币
题目链接题目链接题目链接题目链接
使用二分法+贪心+前缀和
有一个地方不太明白。。
- #include <bits/stdc++.h>
- using namespace std;
- long long array[200010];
- long long qzh[2000010];
- long long q;
- long long n;
- long long x,a;
- long long y,b;
- long long k;
- long long a_b;
- bool judge(long long x);
- int main(void){
- scanf("%lld", &q);
- while(q--){
- scanf("%lld", &n);
- for(long long i = 1; i <= n; i++) scanf("%lld", &array[i]);
- scanf("%lld %lld\n%lld %lld", &x, &a, &y, &b);
- scanf("%lld", &k);
- sort(array,array+n+1,greater<long long>());
- for(long long i = 1; i <= n; i++) printf("%lld ",array[i]);
- for(long long i = 0; i < n; i++) qzh[i+1] = qzh[i] + array[i];
- long long left = 1;
- long long right = n;
- long long ans = n+1;
- if(x < y){
- swap(a,b);
- swap(x,y);
- }
- a_b = (a*b)/__gcd(a,b);
- while(left <= right && left <= n && right >= 1){
- long long mid = (left+right)/2;
- if(judge(mid)){
- ans = min(ans,mid);
- right = mid - 1;
- }else{
- left = mid + 1;
- }
- }
- if(ans == n+1){
- printf("-1\n");
- }else{
- printf("%lld\n",ans);
- }
- memset(array,0,sizeof(array));
- memset(qzh,0,sizeof(qzh));
- n = 0;
- x = 0;
- y = 0;
- a = 0;
- b = 0;
- k = 0;
- }
- return 0;
- }
- [code]bool judge(long long mid){
- int cnta = mid/a;
- int cntb = mid/b;
- int cnts = mid/a_b;
- cnta -= cnts;
- cntb -= cnts;
- long long sum = 0;
- sum += (qzh[cnts]/100)*(x+y);
- sum += (qzh[cnta + cnts] - qzh[cnts])/100*x;
- sum += (qzh[cnts + cnta + cntb] - qzh[cnts+cnta])/100*y;
- if(sum > k) return true;
- else return false;
复制代码
}[/code]
- [b][i][u][color=Red][backcolor=Yellow]这段代码里面的mid/a mid/b mid/a_b操作有点不太懂[/backcolor][/color][/u][/i][/b]
- bool judge(long long mid){
- int cnta = mid/a;
- int cntb = mid/b;
- int cnts = mid/a_b;
- cnta -= cnts;
- cntb -= cnts;
- long long sum = 0;
- sum += (qzh[cnts]/100)*(x+y);
- sum += (qzh[cnta + cnts] - qzh[cnts])/100*x;
- sum += (qzh[cnts + cnta + cntb] - qzh[cnts+cnta])/100*y;
- if(sum > k) return true;
- else return false;
复制代码 |
|