P8161 [JOI 2022 Final] 自学 (Self Study)

· · 题解

题目大意

P8161 [JOI 2022 Final] 自学 (Self Study)

难点坑点

这道题看一下数据范围,用二分做...

储存

此处用 struct 存储更合适:

struct study{
    long long teach,self;
}cla[N];

注意:我在此处把 teach 变量存储最优方案，为节省 best 变量的空间。

取整

因为本题是在求最小值的最大值,故用向上取整。

ll ceil(ll a,ll b){
    return ((a%b)==0)? (a/b) : (a/b+1);
}

二分

判断二分移位:

bool fnd(ll k)
{
    __int128 ok=0;//此处必须用__int128，不然会超
    for(int i=0;i<n;i++){
        if(m*cla[i].teach>=k)//如果符合 课程最优值>k 的条件
            ok+=m-ceil(k,cla[i].teach);//加上寻找二分的数与最优值相除并向上取整
        else 
            ok-=ceil((k-m*cla[i].teach),cla[i].self);//用将k-最优值与自学效果相除
    }
    return ok>=0;如果OK>=0就说明可行
}

进行二分:

while(l<=r){
    ll mid=(l+r)/2;//取中间数
    if(fnd(mid)){//寻找是否符合条件
        l=mid+1;
        ans=mid;
    }
    else r=mid-1;
}

这道题的难点和坑点就主要是这些...

注意事项

完整代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6*3+10;
//快读模板
inline ll read(){
    ll x=0;
    bool flag=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            flag=0;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return (flag?x:~(x-1));
}
ll n=read(),m=read(),l=1,r=1e18,ans;
//定义数组
struct study{
    long long teach,self;
}cla[N];
//向上取整
ll ceil(ll a,ll b){
    return ((a%b)==0)? (a/b) : (a/b+1);
}
bool fnd(ll k){
    __int128 ok=0;
    for(int i=0;i<n;i++){
        if(m*cla[i].teach>=k)
            ok+=m-ceil(k,cla[i].teach);
        else 
            ok-=ceil((k-m*cla[i].teach),cla[i].self);
    }
    return ok>=0;
}
int main(){
    for(int i=0;i<n;i++)
        cla[i].teach=read();
    for(int i=0;i<n;i++){
        cla[i].self=read();
        cla[i].teach=max(cla[i].teach,cla[i].self);//teach存放最好的方案
    }
   //进行二分
    while(l<=r){
        ll mid=(l+r)/2;
        if(fnd(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%lld",ans);
    return 0;
}

附：AC记录