<题目链接>
题目大意：
一家公司想让n个人给他们的产品评论，所以依次去找这n个人，第i个人会评论当且仅当已经有ai个人评论或他确实对这个产品感兴趣，但是这n个人都不对这个产品感兴趣，问这个公司至少要说服几个人对该产品该兴趣才能至少收到m个人的评论。
解题分析：
直接二分答案，然后按顺序进行判断，如果ai大于当前评论的人就说服该人，这里用到了贪心的思想(本题的关键)，因为说服该人能够提供评论数的贡献，所以越早做贡献能够带来更多的贡献，然后根据评论的人数与m的比较来控制二分答案的方向。
#include <cstdio>
using namespace std; const int M =2e5+;
int n,m;
int arr[M];
bool check(int x){
int res=; //res代表当前的评论数
for(int i=;i<=n;i++){
if(arr[i]<=res)res++;
else if(arr[i]>res&&x>){ //劝说该人
x-=;
res++;
}
}
return res>=m;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&arr[i]);
}
int l=,r=n;
int ans=;
while(l<=r){ //直接二分答案，枚举需要劝说的人的数量
int mid=(l+r)>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
return ;
}
2018-11-04