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