二分

题意:

疫情期间,牛牛宅在家里无事可做,于是就在网上买了n本书,每本书都有一个知识值为ai。每读一本书,牛牛的知识力就会上升ai点。当然了,因为牛牛的精力也是有限的,如果同一天连续读k本书,获得的知识力只能增加ai-k+1点。比如第一天看了知识值为5的书,那么牛牛会获得5点知识力,如果这一天在继续看另一本知识值为5的书,只能获得4点知识力,如果看了前面两本书后在继续看一本知识值为2的书,就只能获得0点知识力。牛牛想知道如果他要获得m点知识力,最少需要看几天。

注意:看书不需要按顺序,一本书只能看一次,书可以不看完,只要看就会增加知识力,当书增加的知识力为负时候可以选择不看,可以认为看完一本书是一瞬间的事情,看完后书就会消失。
输入描述:
第一行输入一个n(1≤n≤106)和m(1≤m≤109),第二行输入每本书的知识值ai(0≤ai≤109)。
输出描述:
输出最少要多少天才能获得大于等于m点的知识力,如果无法获得,请输出-1。

分析:

我们要求到达m的最少时间。
直接求解是很困难的,因为仔细分析后我们发现我们并不能贪心。动态规划等也没有头绪,因此考虑到二分答案进行求解。刚好这题也满足二分答案的一切要求,单调且连续

那很好,我们可以二分时间left = 1,right = 1e9,mid = (left+right)>>1
如此,套用二分模板。每次不过验证一次mid秒内是否可以达到或者超过m

那么关键就在于如何验证判断了check(int mid)

其实我们仔细想想,对于n本书,要求m天内读完,我们可以想第一天读哪些书,第二天读哪些书,第三天读哪些书。。。。。。
但是我们还可以这样想,有那些书我是放在当天第一本读的,有哪些书我是放在当天第二本读的。。。。。。
这样看待给了我们一个突破口,注意到题目中的这样一句话:当书增加的知识力为负时候可以选择不看
那我们假设 这一天我们看书顺序是这样的:
6,4,2,3
我们看最终的收益是多少:6+3+0+0 = 9
那如果我们这样放呢:6,4,3,2
收益为:6+3+1+0 = 10
有没有发现什么?
也就是说,如果我们不考虑当书增加的知识力为负时候可以选择不看这一条件的话,
假设我们今天要看4本书(上例)那么我们最终的收获为sum - (0+3)*4/2
对否?那么重点,有了这一句话:当书增加的知识力为负时候可以选择不看
那么当我把小的数放在后面时,他会更早的面临减到零一下的情况,这种情况就不减了!!也就是说我们实际上减的数目是要小于(0+k-1)*k/2的!!!!!!!!!
这种情况下,我们的收益最大

如此我们也差不多知道了,如何验证,请注意代码就好了

代码如下,注意细节 :

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
const int max_n = 1e6 + 100;
ll a[max_n];
ll n, m;

bool check(int mid) {
    ll res = 0, tol = 0, cur = 0;
    for (int i = 1;i <= n;i++) {
        res += max(0LL, a[i] - tol);cur++;
        if (cur == mid) {
            cur = 0;tol++;
        }
    }return res >= m;
}

int main() {
    ios::sync_with_stdio(0);cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a + 1, a + 1 + n, greater<ll>());
    ll l = 1;ll r = 1e9;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid))r = mid;
        else l = mid + 1;
    }if (r > n)cout << -1 << endl;
    else cout << r << endl;
}