FZU 2203 单纵大法好（二分）

悠悠 2022-06-14 05:56 150阅读 0赞

题目链接：  
[Fzu 2203][]

题解：  
二分。  
问你老S最晚将被哪个炮弹第一次击中？显然符合答案单调性。二分一下位置在check一下就可以了。

代码：

//#include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    typedef long long ll;
    int w,num,len;
    const int N=200000+10;
    int a[N]; 
    int b[N];
    int check(int n)
    { 
        for(int i=1;i<=n;i++)b[i]=a[i];
        sort(b+1,b+1+n);
        int cnt = 0;
        b[0] = 0;
        b[n+1] = w+1; 
        for(int i=0;i<=n;i++){
            cnt+=(b[i+1]-b[i])/(len+1); 
        }
        if(cnt >= num) return 1;
        return 0;
    }
    int main()
    {
        while(cin>>w>>num>>len)//地图长度，战舰数，战舰长度 
        {       
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)//炮弹的位置 
            {
                scanf("%d",&a[i]);
            } 
            int l = 1, r = n;
            int mid;
            while(l<=r)
            { 
                mid = (l+r)>>1;
                if(check(mid)){ 
                    l = mid+1;
                }
                else
                    r = mid-1;
            }
            if(check(n))  puts("-1");
            else cout<<l<<endl;
        }
        return 0;
    }

[Fzu 2203]: http://acm.fzu.edu.cn/problem.php?pid=2203

发表评论取消回复

表情：

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

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

相关阅读

相关 Java实现 LeetCode 551 学生出勤记录 I（暴力大法好）

551. 学生出勤记录 I 给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符： ‘A’ : Absent，缺勤 ‘L’ : Late，迟到 ‘

男娘i/ 2023年05月28日 09:53/ 0 赞/ 16 阅读

相关 Immutable.js 大法究竟好在哪？

前一段时间群里有小伙伴问 lucifer 我一个问题：”immutablejs 是什么？有什么用？“。我当时的回答是：`immutablejs 就是 tree + sh

た入场券/ 2023年02月26日 14:25/ 0 赞/ 30 阅读

相关图形渲染有锯齿怎么办？MSAA大法好

众所周知，走样是图形渲染的一大问题，其主要成因是低频采样无法完美呈现高频信号，因而形成了图形混叠，也就是我们所说的锯齿。图形转化成图像的过程，是一个将连续信号经过采样转化成

缺乏、安全感/ 2022年12月15日 11:16/ 0 赞/ 277 阅读

相关 FZu 2134

/该题本来是可以用树状数组写的但是个人觉得简单，就用普通方法直接AC了， / include<iostream> include<

短命女/ 2022年08月10日 15:37/ 0 赞/ 35 阅读

相关 FZU 2203 单纵大法好（二分）

题目链接： [Fzu 2203][] 题解：二分。问你老S最晚将被哪个炮弹第一次击中？显然符合答案单调性。二分一下位置在check一下就可以了。代码：

悠悠/ 2022年06月14日 05:56/ 0 赞/ 151 阅读

相关 HDU-2203

亲和串 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

￡神魔★判官ぃ/ 2022年05月27日 11:26/ 0 赞/ 159 阅读

相关 FZU-2271——X

Problem 2271 X Accept: 394 Submit: 1635 Time Limit: 1500 mSec Memory Limit : 3

旧城等待，/ 2022年05月19日 00:19/ 0 赞/ 171 阅读

相关表达式求值——————Python大法好！

朴素的表达式求值算法加减乘除，用py来写的用双栈来实现就可以我后续会进行C/C++代码的补充；先来看一下python的写法第一种直接模拟双栈

墨蓝/ 2022年03月31日 13:22/ 0 赞/ 189 阅读

相关 FJ的字符串（递归大法好）

题目描述： FJ在沙盘上写了这样一些字符串： A1 = “A” A2 = “ABA” A3 = “ABACABA” A4 = “ABACABADABACABA”

悠悠/ 2022年03月16日 12:13/ 0 赞/ 201 阅读

相关 PAT-1058 选择题 (20 分)STL大法好

批改多选题是比较麻烦的事情，本题就请你写个程序帮助老师批改多选题，并且指出哪道题错的人最多。输入格式：输入在第一行给出两个正整数 N（≤ 1000）和 M（≤ 10

我会带着你远行/ 2022年01月30日 08:23/ 0 赞/ 223 阅读