【篮球杯】二分青蛙过河

妖狐艹你老母 2024-03-26 16:19 97阅读 0赞

**日常二分不会check，很寄啊，感觉这道题好难，考场肯定做不出来的**

题意：

![4039fb6f6249f47d8d613a645f720dde.png][]

思路：

首先确实是一眼二分跳跃能力了，问题在于，我们有了跳跃能力值，怎么去check呢

设跳跃能力为k，结论是，不存在一个区间长度为k，其区间和小于2\*x的区间

如何证明呢？

反证法

如果存在一个长度为k，其区间和小于2\*x

那么我们要经过这个区间2\*x次，每次必然会使该区间**至少-1，**那么该区间和必须不能小于2\*x

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10;
    
    int n,x;
    int a[mxn],sum[mxn];
    bool check(int mid){
        for(int i=1;i<=n-mid;i++){
            if(sum[i+mid-1]-sum[i-1]<2*x) return false;
        }
        return true;
    }
    void solve(){
        cin>>n>>x;
        for(int i=1;i<n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
        int l=1,r=n;
        int ans;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        cout<<ans<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4039fb6f6249f47d8d613a645f720dde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/90670ebd61bd48c993fe170200202a3e.png

发表评论取消回复

表情：

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

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

相关阅读

相关【篮球杯】二分青蛙过河

日常二分不会check，很寄啊，感觉这道题好难，考场肯定做不出来的题意： ![4039fb6f6249f47d8d613a645f720dde.png][] 思路：

妖狐艹你老母/ 2024年03月26日 16:19/ 0 赞/ 98 阅读

相关 leetcode403 青蛙过河

一只青蛙想要过河。假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。青蛙可以跳上石头，但是不可以跳入水中。给定石子的位置列表（用单

- 日理万妓/ 2023年06月18日 05:54/ 0 赞/ 24 阅读

相关 LeetCode-403 青蛙过河

[LeetCode403][] d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示从 i i i点可以走 j j j步长

短命女/ 2022年12月11日 09:21/ 0 赞/ 201 阅读

相关青蛙过河

青蛙过河 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 1）一条小溪尺寸不大，青蛙可以从

我就是我/ 2022年09月29日 05:22/ 0 赞/ 216 阅读

相关 jquery青蛙过河小游戏源码

[下载地址][Link 1]jquery实现的青蛙过河小游戏源码，js小游戏源码。 ![1630059798.png][] dd: [Link 1]: https

蔚落/ 2022年09月09日 02:07/ 0 赞/ 190 阅读

相关青蛙过河

Problem Description 1）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，石柱L面积只容得下一只青蛙落脚，同样右岸也有一石柱R，石柱R面积也

怼烎@/ 2022年07月13日 03:40/ 0 赞/ 252 阅读

相关 ACM HRBUST - 1186 青蛙过河

滴，集训第二十二天打卡。没想到老师还是开了紫书第十章训练... 我怕是没时间去摸索new group的题目咯... 不过前几天，几天时间磨DP感觉很舒服，果然还是慢

清疚/ 2022年06月10日 02:27/ 0 赞/ 198 阅读

相关快速排序二分查找青蛙过河

数据结构实验之排序八：快速排序 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem

柔情只为你懂/ 2022年05月14日 12:48/ 0 赞/ 219 阅读

相关每日力扣：403. 青蛙过河

package com.sample.suncht.algo; import java.util.; / 403. 青蛙

悠悠/ 2022年02月16日 08:23/ 0 赞/ 300 阅读

相关 P1244 青蛙过河

题目描述有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图所示。n只

本是古典何须时尚/ 2021年11月26日 07:32/ 0 赞/ 320 阅读