GYM 101755 K.Video Reviews 【贪心】+【二分】

Stella981
• 阅读 556

<**题目链接**>

题目大意:

一家公司想让n个人给他们的产品评论,所以依次去找这n个人,第i个人会评论当且仅当已经有ai个人评论或他确实对这个产品感兴趣,但是这n个人都不对这个产品感兴趣,问这个公司至少要说服几个人对该产品该兴趣才能至少收到m个人的评论。

解题分析:

直接二分答案,然后按顺序进行判断,如果ai大于当前评论的人就说服该人,这里用到了贪心的思想(本题的关键),因为说服该人能够提供评论数的贡献,所以越早做贡献能够带来更多的贡献,然后根据评论的人数与m的比较来控制二分答案的方向。

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 const int M =2e5+10;
 5 int n,m;
 6 int arr[M];
 7 bool check(int x){
 8     int res=0;   //res代表当前的评论数 
 9     for(int i=1;i<=n;i++){
10         if(arr[i]<=res)res++;     
11         else if(arr[i]>res&&x>0){     //劝说该人 
12             x-=1;    
13             res++;
14         }
15     }
16     return res>=m;
17 }
18 int main(){
19     scanf("%d%d",&n,&m);
20     for(int i=1;i<=n;i++){
21         scanf("%d",&arr[i]);
22     }
23     int l=0,r=n;
24     int ans=0;
25     while(l<=r){       //直接二分答案,枚举需要劝说的人的数量 
26         int mid=(l+r)>>1;
27         if(check(mid))ans=mid,r=mid-1;
28         else l=mid+1;
29     }
30     printf("%d\n",ans);
31     return 0;
32 }

2018-11-04

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
Codeforces 862B (二分图染色)
<题目链接(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fvjudge.net%2Fproblem%2FCodeForces862B)\题目大意:给出一个有n个点的二分图和n1条边,问现在最多可以添加多少条边使得这个图中不存在自环,重边,并且此图还是一个二
Stella981 Stella981
3年前
Codeforces Round #479 (Div. 3) F. Consecutive Subsequence
标签:DP题目链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F977%2Fproblem%2FF)
Stella981 Stella981
3年前
Codeforces Round #611 (Div. 3)
原题面:https://codeforces.com/contest/1283(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1283)A.MinutesBeforetheNewYear题目大意:给定时间,问距离零点
Stella981 Stella981
3年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
3年前
Magic Potions
题目描述:一堆东西,每次拿出两个不同的东西合。要最终合出来的最多。并且要贪心的买121314.。。1n23.。。http://codeforces.com/gym/100430/attachments/download/2418/20092010summerpetrozavodskcampandrewsta
Stella981 Stella981
3年前
POJ 1195 Mobile phones(二维树状数组)
题目链接:http://poj.org/problem?id1195(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D1195)题意是有四种操作。当n0时:输入一个m表示初始化矩阵(m\m且值都为0)。
Stella981 Stella981
3年前
85D Sum of Medians
传送门(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F85%2Fproblem%2FD)题目Inonewellknownalgorithmoffindingthe_k_\thorderst
Stella981 Stella981
3年前
ASP.NET关闭当前窗口同时打开一个新窗口
阅读:37评论:0作者:Derek(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.cnblogs.com%2Fyeahking%2F)发表于2009111122:15原文链接(https://www.oschina.net/action/GoToLink
Stella981 Stella981
3年前
LeetCode.1029
这是小川的第383次更新,第412篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第245题(顺位题号是1029)。公司计划采访的人数为2N。将第i个人飞往城市A的费用是i0,将第i个人飞到城市B的费用是费用i1。返回将
Stella981 Stella981
3年前
Gym101889B. Buggy ICPC(打表)
比赛链接:传送门(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fgym%2F101889)题目:!(https://oscimg.oschina.net/oscnet/54993c8b5f90544695020de0694c1