牛牛爱学习（小白版）

牛牛爱学习（牛客） 题目链接

https://ac.nowcoder.com/acm/contest/6013/A

题目描述

题目： 疫情期间，牛牛宅在家里无事可做，于是就在网上买了n本书，每本书都有一个知识值为ai。每读一本书，牛牛的知识力就会上升ai点。当然了，因为牛牛的精力也是有限的，如果同一天连续读k本书，获得的知识力只能增加ai-k+1点。比如第一天看了知识值为5的书，那么牛牛会获得5点知识力，如果这一天在继续看另一本知识值为5的书，只能获得4点知识力，如果看了前面两本书后在继续看一本知识值为2的书，就只能获得0点知识力。牛牛想知道如果他要获得m点知识力，最少需要看几天。 注意：看书不需要按顺序，一本书只能看一次，书可以不看完，只要看就会增加知识力，当书增加的知识力为负时候可以选择不看，可以认为看完一本书是一瞬间的事情，看完后书就会消失。

输入描述: 第一行输入一个n(1≤ n ≤10^ 6)和m(1≤ m ≤10^ 9)， 第二行输入每本书的知识值ai(0≤ ai ≤10^ 9)。

输出描述: 输出最少要多少天才能获得大于等于m点的知识力，如果无法获得，请输出-1。

示例1 输入 4 10 4 4 4 4 输出 1

说明 第一天看完四本书知识力增加 4+3+2+1=10

示例2 输入 3 20 8 6 6 输出 3

解题思路

首先，拿到这个问题，肯定都能知道是贪心。但是直接去贪心，你可能会卡在不知道要读几天，更无法确定这n本书该如何分配到这几天里。所以，我们就想能不能确定一下这n本书用几天读完，之后再算算在这几天内读若干本书使知识力不少于m能不能成立，要是成立了，说明假设的天数是允许知识力不小于m，反之不允许。 这么一看，要先假设读书的天数，而且要根据假设天数可行不可行不断刷新假设天数，和二分有点相似。思考一下二分的特征：单调有分界点。对比一下本题，是否存在分界点day，比day小的假设天数都是不能获得不少于m的知识力的；比day大的假设天数都是能获得不少于m的知识力的。显然，天数过少的时候，因为连续读书而损失的知识力就会越来越多，导致无法获得m的知识力；天数过多的时候，确实损失减少了，但是天数变多了，并不是我们要的最优解。（这里实在不理解为什么有分界点，可以取两个极限。天数为1天时，很难获取不少于m知识力；天数为n天，也就是每天一本，意味着书本的全部知识力都可以获取，很容易获取不少于m的知识力。） 总结一下整体思路：先把所有书的知识力从大到小排序，二分的时候，让知识力大的书优先被读，也就是每天读的第一本书一定是当天所读书中知识力最大的书。如图去放入排好序的知识力。不断二分，直到找到分界点

思路解释

Q1：为什么从大到小排序？ A1：（我就是从小到大排序进行的贪心，结果错了，当然错误不止这一个hh。） 先讲一下为什么我会从小到大贪心：考虑把尽可能多的书读完，这样会让知识力尽可能得使用上。说实话，我还真没有从理论上理解为什么这样贪心不对，只能片面理解为：存在这样一种情况，大的知识力因为放的靠后，损失也变多，本来放到前面可以最大化地利用大的知识力，但是放在后面，知识力就可能小于损失，就没有正贡献了，所有不如放在前面让他多做贡献。（总结起来一句话：大的知识力不先用留着过年啊！）理论上的糊弄着讲完了，接下来上个实例反驳一下这种思想是错误的，这更有力度：输入：7 4\n 1 1 1 1 1 1 2\n 正确输出应该是3天，如图（上）；简单起见，我们不去二分验证错误思想，我们直接令时间为3天，看看他的day-consume图是什么样，如图（下） 。通过计算发现，正确思想三天能获得4点知识力，但是由错误的思路图计算得到的知识力是3点，意味着错误思路算出的结果一定不是3，与正确结果不一致，所以这种思想就被否定了。（至于在你还没想出是从小到大还是从大到小贪心如何知道此情况的正确结果，自己用笔试试不就行了，数又不多！）

这样一来我们就排除了从小到大的排序思想。 讨论一下为什么从大到小？就是上面那句话，不先读知识力大的，打算留着过年吗？我们就是为了尽可能多得获取知识力，所以就先读知识力大的。这种思想的真正正确性要么通过严谨的证明，要么就多跑几个实例验证，显然选择第二个。最后发现这是ok的。

Q2：为什么要先把consume=0的时候先排满再顺着往下排呢？ A2：答案包含在上面那个问题的答案里了，就是这种贪心的思想，让消耗少时读大的知识力的书。

AC代码

#include
#define ll long long
using namespace std;
const int N=1e6+10;
int a[N];
bool cmp(int a,int b){
 	return a>b;
}
int main(){
 	int n,ans=-1;//初始化ans=-1，二分没找到分界点ans就未被赋值，直接输出ans就行了，即-1
 	int m;
 	cin>>n>>m;
 	for(int i=0;i>a[i];
 	}
	sort(a,a+n,cmp);
 	int l=1,r=n;
 	while(l