[传送门]

思路:

分析了一下 数据范围 必须是 O(n) 或者 O(nlogn) 这种级别的,由于题目是二分题

所以就一直想怎么二分,想着每次排序之后二分寻找答案？

结果错了

正解

我们 按天数 二分即可

但是防止TL 我们还需要在sort一下增加后的数组 然后从头开始贪心的拿

Code:

/// O nlogn
#include <bits/stdc++.h>
using namespace std;
const int N  = 2e5+10;
typedef long long ll;
ll h[N],a[N],c[N];
ll n,s,l,maxn;

bool check(ll x)
{
    ll sum  = 0;
    for(int i = 0; i<n; i++)
        c[i] = h[i]+x*a[i];

    sort(c,c+n);///果然要排序

    for(int i=n-1; i>=0; i-- )
    {
        if(c[i]<l)break; ///小于限制
        if(sum>=s)break; ///如果已经够了
        sum+=c[i];///然后再加 
    }
    if(sum>=s)return true;
    return false;
}

///对天数进行二分
ll bsearch(ll l, ll r)
{
    while(l<r)
    {
        ll mid = l+r>>1;
        if(check(mid)) r=mid;
        else l = mid+1;
    }
    return l;
}

void solve()
{
    cin>>n>>s>>l;
    for(ll i=0; i<n; i++)
        scanf("%lld",&h[i]);

    for(ll i=0; i<n; i++)
    {
        scanf("%lld",&a[i]);
        ///这个范围划分 可以
        ///要么是订单总量 要么是 单块长度限制
        ///然后取这块能符合的 最长天数
        maxn = max(maxn,max(l,s)/a[i]);
    }
    cout<<bsearch(0,maxn)<<endl;
}
int main()
{
    solve();
    return 0;
}