• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

暑假集训Day9 A(二分答案)

开发技术 开发技术 5小时前 1次浏览

题目链接在这里:Problem – A – Codeforces

这有意思一道二分题,不过确实非常巧妙。

如果是暴力的话我们可以从前开始枚举,每次处理都排一遍序进行判断。时间复杂度是O((n^2)logn)。由于我们要找的是第一个出现问题的回答,也就是说,从某一个点开始往后,每一次的前缀都是有问题的,所以可以用二分去解决。二分题的核心是判断标准,这题的判断标准就是前x个回答隔开的空档是否够塞下k条船。时间复杂度是O(n*(logn)^2)

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=2e5+5;
 4 int n,m,k,len,a[MAX];
 5 int low,high,mid,ans;
 6 bool feasible(int x){
 7     int i,j,an,b[MAX];b[0]=0;
 8     for (i=1;i<=x;i++) b[i]=a[i];
 9     sort(b+1,b+x+1);
10     b[x+1]=n+1;
11     an=(b[1]-b[0])/(len+1);
12     for (i=2;i<=x+1;i++)
13         an+=(b[i]-b[i-1])/(len+1);
14     return an>=k;
15 }
16 int main(){
17     freopen ("a.in","r",stdin);
18     freopen ("a.out","w",stdout);
19     int i,j;
20     scanf("%d%d%d%d",&n,&k,&len,&m);
21     for (i=1;i<=m;i++) scanf("%d",a+i);
22     low=1,high=m;ans=-1;
23     while (low<=high){
24         mid=(low+high)>>1;
25         if (feasible(mid))
26             low=mid+1;
27         else
28             ans=mid,high=mid-1;
29     }
30     printf("%d",ans);
31     return 0;
32 }

 


程序员灯塔
转载请注明原文链接:暑假集训Day9 A(二分答案)
喜欢 (0)