Codeforce div2问题疑惑
题目链接题目链接题目链接题目链接使用二分法+贪心+前缀和
有一个地方不太明白。。
#include <bits/stdc++.h>
using namespace std;
long long array;
long long qzh;
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);
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);
for(long long i = 0; i < n; i++) qzh = qzh + array;
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;
}
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/100)*(x+y);
sum += (qzh - qzh)/100*x;
sum += (qzh - qzh)/100*y;
if(sum > k) return true;
else return false;
}
这段代码里面的mid/a mid/b mid/a_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/100)*(x+y);
sum += (qzh - qzh)/100*x;
sum += (qzh - qzh)/100*y;
if(sum > k) return true;
else return false; 自顶呀呀呀
页:
[1]