P8161 题解

sgl654321 · 2022-02-25 21:41:41 · 题解

传送门

题目大意

定义一个长度为 n 的数组 K 代表理解程度，初始值全为 0。

遍历 m 次，每次遍历到 i，可以选择让 K_i 增加 A_i，或者让任意一个数 K_j 增加 B_j。

求遍历 m 次后，数组 K 中的最小值最大可以是多少。

解题思路

暴力做肯定会超时。粗略思考后或点开标签后，发现可以用二分答案加验证的做法。一般来说，求最大值最小，最小值最大一类的问题，一般都可以使用二分答案加验证的做法。

什么是二分答案加验证？就是一个问题的可行解按某种单调规律排列，只需要二分答案再进行验证，最终就可以得到最优解。

本题答案最小为 1，最大不超过 10^{18}。而且预期越小，是可行解的可能性越大。所以就可以进行二分答案了。

那么二分答案之后怎么验证呢？本题我们可以用贪心法进行验证。

贪心策略：先传入一个目标值。

如果自学比上课更好，那么就去自学，直到达到目标值为止。

如果上课比自学更好，那么看一看仅仅上课能否达到目标值。如果可以，那就尽可能少地去上课。如果达不到目标，那就先上完课，然后再尽可能少地自学。

将自学与上课的总课程数记为 num。如果 num\le n\times m，则该目标值是可行解。反之，就是不可行解。

我们就用第一个样例来举例吧！首先我们不停地二分答案，最终二分答案到了 18 这个数。遍历每一个课程。

• 课程 1：上课的理解程度较高，所以我们优先上课。每一次上课能增加 19 的理解程度，为了达到 18 的理解程度，我们只需要上 1 节课。
• 课程 2：自学的理解程度较高，我们就全部自学。每一次自学能够增加 6 的理解程度，为了达到 18 的理解程度， 我们要自学 3 次。
• 课程 3：上课的理解程度较高，我们优先上课。每一次上课能够增加 5 的理解程度，但即使 3 周都上课，还是无法达到 18 的理解程度。因此，剩下的 3 的理解程度我们需要自学。每一次自学，我们都可以增加 2 的理解程度，所以我们需要再自学 2 次。总共上课和自学，用了 5 节课。

所以，3 门课我们一共使用了 9 节课，刚好用完。经检验，发现没有比这个答案更大的可行解。所以，应该输出 18。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,l,r,ans,num,mid;
struct study{
    long long teach,self;
}a[300010];
long long lesson_num(long long target,long long eta){//eta 代表工作效率
     //工作时间=工作总量/工作效率，向上取整
     if(target%eta==0)return target/eta;
     else return target/eta+1; 
}
bool check(long long target){//target 代表目标 
    num=0;//num代表达到目标所需的上课次数 
    for(int i=1;i<=n;i++){//每一门课都要到达大于等于目标的理解程度 
        if(a[i].self>a[i].teach)//自学比上课好，就绝对去自学 
            num+=lesson_num(target,a[i].self);
        else{//上课理解程度高，优先选择上课 
            if(m*a[i].teach>=target)//仅靠上课，就可以达到目标：）
                num+=lesson_num(target,a[i].teach);
            else{//不仅要上课，还要去自学才能达成目标qwq 
                num+=m;//上课的次数先计算上； 
                num+=lesson_num(target-m*a[i].teach,a[i].self); 
                //剩下的全部自学。 
            }
        }
    //一轮下来，我们就得出所需的上课次数了！
    //如果此时总上课次数已经超标，就不必计算直接返回假值。 
        if(num>n*m)return 0;
    } 
    return 1;

}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].teach);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].self);
    l=1;r=1000000000000000010;
    while(l<=r){//二分答案加验证 
        mid=(l+r)>>1;
        if(check(mid)==true){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

写在最后：管理大大求过。