[牛客] 二分 汀博尔

[传送门]

思路:

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

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

结果错了

正解

我们 按天数 二分即可

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

Code:

/// O nlogn
#include 
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=0; i-- )
    {
        if(c[i]=s)break; ///如果已经够了
        sum+=c[i];///然后再加 
    }
    if(sum>=s)return true;
    return false;
}

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

void solve()
{
    cin>>n>>s>>l;
    for(ll i=0; i