The studio «Lodka Gaming» is engaged in advertising of their new game «.C.O.N.T.E.S.T: Unexpected
Behaviour». The studio’s marketer is planning to communicate with n videobloggers one by one (in the
predetermined order, starting from the 1-st and ending with the n-th), offering them to record a video
review on the game. All people are different and videobloggers are as well, therefore the i-th videoblogger
will record a review in two cases: either he is interested in this game, or there are already at least ai video
reviews on this game.
The studio wants to have at least m video reviews in the Internet. The game designer of «Lodka Gaming»
understands these video reviews possibly would not appear by themselves, so he wants to convince some
video bloggers that they are actually interested in this game. Which minimal number of videobloggers are
needed to be convinced?
Input
The first line contains two integers n and m (1 ≤ n ≤ 200000, 1 ≤ m ≤ n) — the number of videobloggers
and the required number of video reviews.
The second line contains n integers ai (0 ≤ ai ≤ 200000) — the minimal number of video reviews that
should appear in the Internet so that the i-th videoblogger will record a review in case he is not interested
in the game.
Output
Output a single integer — the minimal number of videobloggers who have to be convinced to record a
video review on the game in order to achieve at least m total video reviews in the Internet.
Examples
standard input standard output
7 4
2 1 3 3 4 2 3
1
7 4
2 1 3 3 4 3 2
2
题意：有n个顾客，公司至少需要m个人评论，每个人对应一个 ai,
意味着至少得有 ai 个人评论了，他才会评论；现在可以按顺序说服一些人使其信服（也就是可以让他评论）
，初始状态每个人都不感兴趣（不评论），问最少需要说服多少人才能满足m个人都评论；
不妨先看一下样例：
7 4
2 1 3 3 4 2 3
答案为1；
从第一个人开始，将其说服，现在被说服的有1个人，也就是目前有1人评论；到第二个人，他之前有1个人评论，而 a2==1,所以他也会评论；同理下去……
思路：二分最终的答案：因为最大需要说服的人的个数就是m ，所以我们每次二分下去，当去检验某个答案时：从头开始遍历，如果说服的名额还充足，就将这个人说服，因为现在说服会增加评论量，对以后会产生贡献，所以结果不会变坏；当满足m个人时，那么将上界缩小，再次二分下去，同理对于下界放大的情况
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 500003
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int a[maxn];
int n, m;
bool judg(int x) {
int res = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= res)res++;
else if (x) {
res++;
x--;
}
if (res == m)return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
int i, j;
for (i = 1; i <= n; i++)cin >> a[i];
int L = 0, R = m;
int mid;
int res = m;
while (L <= R) {
mid = (L + R) >> 1;
if (judg(mid)) {
R = mid - 1;
res = mid;
}
else L = mid + 1;
}
cout << res << endl;
}