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

dzy15373891653 · 2025-01-26 15:46:07 · 题解

题目传送门

//本题考查二分答案再带一点点贪心 
#include<iostream>
#define int long long//将int类型转为long long 

using namespace std;

const int N = 3e5+5;

int n,m,a[N],b[N],c[N],ans;

bool check (int x){//判断当x为最小值时，符不符合条件 
     __int128 cnt = 0;//注意开__int128因为下面当b[i]特别小时就溢出了，因为1e9*1e9+1e9会爆long long; 

    for (int i = 1;i <= n;i ++){
        if (c[i] * m >= x){//如果说它能在上课的时间达到目标，就看它还能翘多少次课去帮其它学科 
            cnt += (c[i] * m - x) / c[i];//c[i]*m表示总共上课能获得多少理解程度，再减去目标程度，剩下的除以它，看能剩下多少天能去帮别的学科 
        }
//      if ((c[i] * m - x) % c[i] != 0) cnt --;
    }
    for (int i = 1;i <= n;i ++){
        if (c[i] * m < x){//如果说它不能在上课的时间达成目标，那么它就需要其它学科的帮助 
            cnt -= (x - c[i] * m + b[i] - 1) / b[i];//x-c[i]*m表示还差多少才能达到目标，+b[i]-1是向上取整，用if也行，不信带个数进去试试就知道了，最后再除以b[i](注意这里只能是b[i]，因为是其它学科多余时间的帮助，不是自学) 
        }
//      if ((x - c[i] * m) % b[i] != 0) cnt --;
    }

    return cnt >= 0;//如果说时间够用，那么方案可行 
}

signed main(){

    cin >> n >> m;

    for (int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    for (int i = 1;i <= n;i ++){
        cin >> b[i];

        c[i] = max (a[i],b[i]);//我们肯定是选获得理解能力大的先执行，所以用个数组存起来 
    }

    int l = 1,r = 1e18;//注意r要开1e18因为m*c[i]是最大的，1e9*1e9
    while (l <= r){

        int mid = (l + r ) >> 1;//右移一位等于除以二，二分枚举中间可能的最大值 
        if (check(mid)){
            ans = max (ans,mid);//取最大值 
            l = mid + 1;//如果方案可行就往右面找有没有更大的 
        }else{
            r = mid - 1;//否则就往左面找看小一点的符不符合 
        }

    }

    cout << ans << '\n';//输出答案 

    return 0;//华丽结束 
}