鱼C论坛

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

Codeforce div2问题疑惑

[复制链接]
发表于 2019-12-3 18:39:59 | 显示全部楼层 |阅读模式
20鱼币
题目链接题目链接题目链接题目链接

使用二分法+贪心+前缀和
有一个地方不太明白。。
  1. #include <bits/stdc++.h>

  2. using namespace std;

  3. long long array[200010];
  4. long long qzh[2000010];
  5. long long q;
  6. long long n;
  7. long long x,a;
  8. long long y,b;
  9. long long k;
  10. long long a_b;

  11. bool judge(long long x);
  12. int main(void){
  13.     scanf("%lld", &q);
  14.     while(q--){
  15.         scanf("%lld", &n);
  16.         for(long long i = 1; i <= n; i++) scanf("%lld", &array[i]);
  17.         scanf("%lld %lld\n%lld %lld", &x, &a, &y, &b);
  18.         scanf("%lld", &k);
  19.         sort(array,array+n+1,greater<long long>());
  20.         for(long long i = 1; i <= n; i++) printf("%lld ",array[i]);
  21.         for(long long i = 0; i < n; i++) qzh[i+1] = qzh[i] + array[i];
  22.         long long left = 1;
  23.         long long right = n;
  24.         long long ans = n+1;
  25.         if(x < y){
  26.             swap(a,b);
  27.             swap(x,y);
  28.         }
  29.         a_b = (a*b)/__gcd(a,b);
  30.         while(left <= right && left <= n && right >= 1){
  31.             long long mid = (left+right)/2;
  32.             if(judge(mid)){
  33.                 ans = min(ans,mid);
  34.                 right = mid - 1;
  35.             }else{
  36.                 left = mid + 1;
  37.             }
  38.         }
  39.         if(ans == n+1){
  40.             printf("-1\n");
  41.         }else{
  42.             printf("%lld\n",ans);
  43.         }
  44.         memset(array,0,sizeof(array));
  45.         memset(qzh,0,sizeof(qzh));
  46.         n = 0;
  47.         x = 0;
  48.         y = 0;
  49.         a = 0;
  50.         b = 0;
  51.         k = 0;
  52.     }
  53.     return 0;
  54. }

  55. [code]bool judge(long long mid){
  56.     int cnta = mid/a;
  57.     int cntb = mid/b;
  58.     int cnts = mid/a_b;
  59.     cnta -= cnts;
  60.     cntb -= cnts;
  61.     long long sum = 0;
  62.     sum += (qzh[cnts]/100)*(x+y);
  63.     sum += (qzh[cnta + cnts] - qzh[cnts])/100*x;
  64.     sum += (qzh[cnts + cnta + cntb] - qzh[cnts+cnta])/100*y;
  65.     if(sum > k) return true;
  66.     else return false;
复制代码

}[/code]

  1. [b][i][u][color=Red][backcolor=Yellow]这段代码里面的mid/a mid/b mid/a_b操作有点不太懂[/backcolor][/color][/u][/i][/b]
  2. bool judge(long long mid){
  3.     int cnta = mid/a;
  4.     int cntb = mid/b;
  5.     int cnts = mid/a_b;
  6.     cnta -= cnts;
  7.     cntb -= cnts;
  8.     long long sum = 0;
  9.     sum += (qzh[cnts]/100)*(x+y);
  10.     sum += (qzh[cnta + cnts] - qzh[cnts])/100*x;
  11.     sum += (qzh[cnts + cnta + cntb] - qzh[cnts+cnta])/100*y;
  12.     if(sum > k) return true;
  13.     else return false;
复制代码

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-12-3 21:28:25 From FishC Mobile | 显示全部楼层
自顶呀呀呀
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2025-7-8 05:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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