玄关求调
查看原帖
玄关求调
644963
ln001楼主2024/1/21 12:47

10pts

// Problem: P8775 [蓝桥杯 2022 省 A] 青蛙过河
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8775
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include "bits/stdc++.h"
#define ll long long
#define fst                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define f(x, y, z) for (register ll x = (y); x <= (z); x++)
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 10, inf = 0x3f;
ll n, x;
ll h[N];
ll qz[N];
bool check(ll y)
{
    for (ll i = 1; i + y - 1 <= n; i++)
    {
        if (qz[i + y - 1] - qz[i - 1] < x)
            return 0;
    }
    return 1;
}
signed main()
{
    fst;
    cin >> n >> x;
    x *= 2;
    f(i, 1, n - 1) cin >> h[i];
    qz[n] = h[n] = INF;
    qz[0] = 0;
    f(i, 1, n - 1) qz[i] = qz[i - 1] + h[i];
    ll l = 1, r = n, ans = n;
    while (l <= r)
    {
        ll mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid - 1;
            ans = mid;
        }
        l = mid + 1;
    }
    cout << ans;
    return 0;
}
2024/1/21 12:47
加载中...