6 条题解

  • 1
    @ 2026-10-23 7:50:00

    逆天二分答案+线段树solution,不必多讲了。 两只log做法,只能说是唐完了。

    双log?没开玩笑吧。

    #include <bits/stdc++.h>
    #define int unsigned long long
    using namespace std;
    const int N = 1e5 + 5;
    int n, m, t[N], f[N][2], sum[N];
    struct tree {
    	int l, r;
    	int val;
    }tr[N << 2];
    void pushup(int u) {
    	tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
    }
    void build(int u, int l, int r) {
    	tr[u].l = l, tr[u].r = r;
    	if(l == r) {
    		tr[u].val = -1;
    		return ;
    	}
    	int mid = (l + r) >> 1;
    	build(u << 1, l, mid);
    	build(u << 1 | 1, mid + 1, r);
    	pushup(u);
    }
    void update(int u, int p, int x) {
    	if(tr[u].l == tr[u].r) {
    		tr[u].val = x;
    		return ;
    	}
    	int mid = (tr[u].l + tr[u].r) >> 1;
    	if(p <= mid) update(u << 1, p, x);
    	else update(u << 1 | 1, p, x);
    	pushup(u);
    }
    long long query(int u, int l, int r) {
    	if(tr[u].l > r || tr[u].r < l || l > r) return -1;
    	if(tr[u].l >= l && tr[u].r <= r) {
    		return tr[u].val;
    	}
    	int mid = (tr[u].l + tr[u].r) >> 1;
    	if(r <= mid) return query(u << 1, l, r);
    	if(l > mid) return query(u << 1 | 1, l, r);
    	return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
    bool check(int mxx) {
    	memset(f, 0, sizeof(f));
    	int M = mxx;
    	build(1, 1, n);
    	for(int i=1; i<=M; ++i) {
    		f[i][0] = max(f[i - 1][0], f[i - 1][1]), f[i][1] = f[i - 1][1] + t[i];
    		update(1, i, f[i][0] - sum[i]);
    	}
    	for(int i=M+1; i<=n; ++i) {
    		f[i][0] = max(f[i - 1][0], f[i - 1][1]);
    		f[i][1] = query(1, i - M, i - 1) + sum[i]; 
    		update(1, i, f[i][0] - sum[i]);
    	}
    	int ans = max(f[n][0], f[n][1]);
    	if(sum[n] - ans <= m) return 1;
    	else return 0;
    }
    signed main() {
    	ios :: sync_with_stdio(0);
    	cin.tie(0), cout.tie(0);
    	cin >> n >> m;
    	for(int i=1; i<=n; ++i) {
    		cin >> t[i];
    		sum[i] = sum[i - 1] + t[i];
    	}
    	bool flag = 0;
    	for(int i=1; i<=n; ++i) {
    		if(t[i] <= m) flag = 1;
    	}
    	if(sum[n] <= m) {
    		cout << 0;
    		return 0;
    	}
    	if(!flag) {
    		cout << n;
    		return 0;
    	} 
    	int L = 0, R = n + 1;
    	while(L <= R) {
    		int mid = (L + R) >> 1;
    		if(check(mid)) {
    			R = mid - 1;
    		}
    		else {
    			L = mid + 1;
    		}
    	}
    	cout << L;
    	return 0;
    } 
    

    信息

    ID
    288
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    77
    已通过
    20
    上传者