6 条题解
-
1
逆天二分答案+线段树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
- 上传者