codeforces 567D 二分

末蓝、 2022-08-04 05:09 110阅读 0赞

满足二分的条件，如果当前的断点不符合条件，那么后面的一定不符合条件，如果当前的符合条件，那么后面的可能还有符合条件的。

二分的过程中对断点进行排序，判断每个区间能放多少船只，总和加起来，判断是不是小于k。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int n,m,a,k;
    int x[200020];
    int xx[200020];
    
    bool check(int t)
    {
        ll res=0;
        memcpy(xx,x,sizeof(int)*(t+1));
        xx[0]=0,xx[t+1]=n+1;
        sort(xx,xx+t+2);
        for(int i=1;i<=t+1;i++)
        {
            if(xx[i]-xx[i-1]-1>=a) res+=(xx[i]-xx[i-1])/(a+1);
        }
        return res>=k;
    }
    
    int main()
    {
        n=in(),k=in(),a=in();
        m=in();
        for(int i=1;i<=m;i++)
        {
            x[i]=in();
        }
        int l=1,r=m;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                l=mid+1;
            }
            else r=mid-1;
        }
        printf("%d\n",l==m+1?-1:l);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关 CodeForces 55D

题意略。思路：本题可以说是醉翁之意不在酒了。要解开本题有几个关键点： 1.意识到数X = An An-1 An-2 An-3 .... A2 A1能被\{An,An-

深碍√TFBOYSˉ_/ 2023年08月17日 16:37/ 0 赞/ 75 阅读

相关 codeforces 567C

mp2存放每个数当中间的数的次数，对每个数，如果有a\[i\]%k==0，那么ans就加上mp2\[a\[i\]/k\]，mp表示这个数当第一个数的次数，对每个数，如果有a\[

深碍√TFBOYSˉ_/ 2022年08月04日 05:10/ 0 赞/ 103 阅读

相关 codeforces 567D 二分

满足二分的条件，如果当前的断点不符合条件，那么后面的一定不符合条件，如果当前的符合条件，那么后面的可能还有符合条件的。二分的过程中对断点进行排序，判断每个区间能放多少

末蓝、/ 2022年08月04日 05:09/ 0 赞/ 111 阅读

相关 codeforces B. Pasha and Tea二分

[http://codeforces.com/contest/557/problem/B][http_codeforces.com_contest_557_problem_B]

悠悠/ 2022年08月01日 18:17/ 0 赞/ 115 阅读

相关 codeforces 672D 二分

D. Robin Hood time limit per test 1 second memory limit per test 256 megabytes inpu

ゞ浴缸里的玫瑰/ 2022年07月24日 07:24/ 0 赞/ 102 阅读

相关 Codeforces 496D

题意 -------------------- 进行若干场比赛，每次比赛两人对决，赢的人得到1分，输的人不得分，先得到t分的人获胜，开始下场比赛，某个人率先赢下s场比赛

你的名字/ 2022年07月16日 14:15/ 0 赞/ 77 阅读

相关 CodeForces 702B Powers of Two（二分）

B. Powers of Two time limit per test 3 seconds memory limit per test 256 megabytes

深藏阁楼爱情的钟/ 2022年02月25日 11:38/ 0 赞/ 98 阅读

相关 Codeforces Round #567 (Div. 2)自闭记

嘿嘿嘿，第一篇文章，感觉代码可以缩起来简直不要太爽打个div2发挥都这么差... 平均一题fail一次，还调不出错，自闭了又一次跳A开B，又一次B傻逼错误调不出

我就是我/ 2021年11月26日 15:26/ 0 赞/ 170 阅读

相关 CodeForces - 1087D

CodeForces - 1087D https://vjudge.net/problem/2115151/origin 2\和/叶子结点的个数 includ

红太狼/ 2021年10月30日 01:36/ 0 赞/ 165 阅读

相关 Codeforces 749D Leaving Auction（set+二分）

题意：有几个人在拍卖场竞价，一共有n次喊价，有q个询问，每一个询问有一个num，接下来num个人从这次拍卖中除去，问对于每一个询问减掉num个人后是谁赢了拍卖，最小的价格是多

骑猪看日落/ 2021年10月18日 08:36/ 0 赞/ 191 阅读