问题标题: 酷町堂：4064 倒霉熊吃鱼

Question

0

已解决

汪宇航

新手启示者

跪求思路，凡是给了正确思路/核心的人均分100豆！！！

汪宇航在2021-09-25 10:55:56追加了内容

设a个人给了思路/核心，各分得100/a豆

汪宇航在2021-09-25 11:25:04追加了内容

#include <bits/stdc++.h>
using namespace std;
long long n,a[500005],A,B;
bool ch(int t){
    int sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]-A*t>0){
            sum+=(a[i]-A*t+B-1)/B;
            if(sum>t){
                return 0;
            }
        }
        
    }
    return 1;
}
int bn(int l,int r){
    while(l<r){
        int mid=(l+r)/2;
        if(ch(mid))r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<bn[1,500000];
    return 0;
}
WA0

@李显晨@李显晨

酷町豆刷题求解 C++ 4条评论 3 年，2 月前

Answer 1

已采纳

李显晨

中级启示者

王老师说这道题的时候，说成了倒霉鱼吃熊……

李显晨在2021-09-25 11:03:17追加了内容

这题要用二分

全局：
long long n,a[500005],A,B;
bool check(int t){
    int sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]-A*t>0){
			sum+=(a[i]-A*t+B-1)/B;
            if(sum>t) return false;
		}
	}
    return true;
}
int binary(int l,int r){  
    while(l<r){  
        int mid=(l+r)/2;
        if(check(mid)) r=mid; 
        else l=mid+1;
    }  
    return l;
} 
主函数：
输入n、A、B;
循环(1~n) 输入a[i];
cout<<binary(1,500000);

Answer 2

汪恺恒

中级启示者

二分答案，注意除法的向下取整

Answer 3

褚俊皓

新手天翼

二分：

bool check(int t){
    int sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]-A*t>0){
            sum+=(a[i]-A*t+B-1)/B;
        }
        if(sum>t) return false;
    }
    return true;
}

问题标题: 酷町堂：4064 倒霉熊吃鱼

3 个回答: