鱼C论坛

 找回密码
 立即注册
查看: 2909|回复: 1

Codeforce div2问题疑惑

[复制链接]
发表于 2019-12-3 18:39:59 | 显示全部楼层 |阅读模式
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]这段代码里面的mid/a mid/b mid/a_b操作有点不太懂[/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;

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-12-3 21:28:25 From FishC Mobile | 显示全部楼层
自顶呀呀呀
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-16 13:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表