Codeforce div2问题疑惑

ksdeer

题目链接题目链接题目链接题目链接

使用二分法+贪心+前缀和
有一个地方不太明白。。

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. long long array[200010];
   
6. long long qzh[2000010];
   
7. long long q;
   
8. long long n;
   
9. long long x,a;
   
10. long long y,b;
    
11. long long k;
    
12. long long a_b;
    
13. 
    
14. bool judge(long long x);
    
15. int main(void){
    
16.     scanf("%lld", &q);
    
17.     while(q--){
    
18.         scanf("%lld", &n);
    
19.         for(long long i = 1; i <= n; i++) scanf("%lld", &array[i]);
    
20.         scanf("%lld %lld\n%lld %lld", &x, &a, &y, &b);
    
21.         scanf("%lld", &k);
    
22.         sort(array,array+n+1,greater<long long>());
    
23.         for(long long i = 1; i <= n; i++) printf("%lld ",array[i]);
    
24.         for(long long i = 0; i < n; i++) qzh[i+1] = qzh[i] + array[i];
    
25.         long long left = 1;
    
26.         long long right = n;
    
27.         long long ans = n+1;
    
28.         if(x < y){
    
29.             swap(a,b);
    
30.             swap(x,y);
    
31.         }
    
32.         a_b = (a*b)/__gcd(a,b);
    
33.         while(left <= right && left <= n && right >= 1){
    
34.             long long mid = (left+right)/2;
    
35.             if(judge(mid)){
    
36.                 ans = min(ans,mid);
    
37.                 right = mid - 1;
    
38.             }else{
    
39.                 left = mid + 1;
    
40.             }
    
41.         }
    
42.         if(ans == n+1){
    
43.             printf("-1\n");
    
44.         }else{
    
45.             printf("%lld\n",ans);
    
46.         }
    
47.         memset(array,0,sizeof(array));
    
48.         memset(qzh,0,sizeof(qzh));
    
49.         n = 0;
    
50.         x = 0;
    
51.         y = 0;
    
52.         a = 0;
    
53.         b = 0;
    
54.         k = 0;
    
55.     }
    
56.     return 0;
    
57. }
    
58. 
    
59. [code]bool judge(long long mid){
    
60.     int cnta = mid/a;
    
61.     int cntb = mid/b;
    
62.     int cnts = mid/a_b;
    
63.     cnta -= cnts;
    
64.     cntb -= cnts;
    
65.     long long sum = 0;
    
66.     sum += (qzh[cnts]/100)*(x+y);
    
67.     sum += (qzh[cnta + cnts] - qzh[cnts])/100*x;
    
68.     sum += (qzh[cnts + cnta + cntb] - qzh[cnts+cnta])/100*y;
    
69.     if(sum > k) return true;
    
70.     else return false;

复制代码

}[/code]

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

复制代码

ksdeer

自顶呀呀呀