两句话

用户名：uq_42709742140

访问量：3393

签　名：

等　　级
排　　名	2787
经　　验	2149
参赛次数	0
文章发表	37
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Seq2Seq的学习总结
浏览：50

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2667: 蓝桥杯2022年-青蛙过河（二分法查找）记录题目思路

　　作者: 两句话　　　　发表时间：2024-03-28 18:54:57 浏览：75　|　评论：0　

**大佬代码：**用区间长度去测试能否满足条件，不能就再加，能就减，看能不能更小
```cpp
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
ll a[N] , sum[N];
ll n , x ,ans;

bool test(int mid)
{//测试长度为mid的区间是否满足题意
    for(int i = 1;i <= n - mid;i ++)
    {
        int j = i + mid - 1;
        if(sum[j] - sum[i - 1] < 2*x)   return false;
    }
    return true;
}

int main()
{
    cin>>n>>x;
    for(int i = 1;i < n;i ++)
    {
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }

ll l = 1, r = n;
    ll mid = l + (r - l) / 2;
    while(l <= r)
    {
        if(test(mid))
        {//如果满足
            ans = mid;
            r = mid - 1;	//再次尝试更小的区间是否可行
            mid = l + (r - l) / 2;
        }
        else
        {//不满足
            l = mid + 1;	//适当扩大当前区间长度
            mid = l + (r - l) / 2;
        }
    }
    cout<<ans<<endl;
    return 0;
}
```
**自己的思路（乱七八糟）**：先找到前缀和满足条件的区间，再测试这个区间是否对整个数组都使用，不适用就区间长度+1再测试，最后求所有满足过河条件的区间里最小的那个，但是会超时，只有97%正确
```cpp
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
ll stone[N], sum[N];
ll n , x , step = 0x3f3f3f;

bool test(int t)
{//测试
    for(int i = 1;i <= n - t;i ++)
    {
        int j = i + t - 1;
        if(sum[j] - sum[i - 1] < 2*x)   return false;
    }
    return true;
}

int main()
{
    cin>>n>>x;
    sum[0] = 0;
    for(int i = 1;i <= n - 1;i ++)
    {
        cin>>stone[i];
        sum[i] = sum[i - 1] + stone[i];
    }

ll t = 2*x;
    ll l , r , cnt;
    for(int i = 1, j = i;i < n&&j < n;i = r + 1)
    {
        l = i , cnt = 0;
        while(sum[j] - sum[i - 1] <= t && j < n )  
        {
            cnt = sum[j] - sum[i - 1];
            j++;
        }

if(i == 0 && j == n && cnt < t) 
        {//无满足条件的区间
            step = n;
            break;
        }
        else  r = j - 1;

if(cnt < t && sum[j] - sum[i - 1] > t)   r = j;
        // cout<<l <<' '<<r<<endl;
        ll t = r - l + 1;
        bool ans = test(t);
        while(!ans)
        {
            t++;
            ans = test(t);
        }
        step = min(step , t);
    }

cout<<step<<endl;
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

两句话

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【密码】（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2667: 蓝桥杯2022年-青蛙过河（二分法查找）记录题目思路

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1157题解

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

test 2

防御导弹（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

两句话

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【密码】 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2667: 蓝桥杯2022年-青蛙过河（二分法查找）记录题目思路

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1157题解

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

test 2

防御导弹 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

【密码】（C语言代码）

　　评论区

防御导弹（C语言代码）