SGU 148 枚举

题意

传送门 SGU 148 B-Station

题解

自顶而下枚举层 i i i，计算摧毁 i → n i\rightarrow n i→n 需要的最小花费。暴力计算 O ( n 2 ) O(n^2) O(n2)。

令 s u m [ i + 1 ] sum[i+1] sum[i+1] 代表 0 ⋯ i 0\cdots i 0⋯i 关于 L L L 的前缀和。那么枚举 i i i 时，实际上需要花钱摧毁的位置 j j j 满足 s u m [ j + 1 ] − s u m [ i ] ≤ L [ i ] sum[j+1]-sum[i]\leq L[i] sum[j+1]−sum[i]≤L[i]。前缀和单调不降，那么需要花钱摧毁的集合满足单调性。 O ( n ) O(n) O(n) 求解即可。

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 15E3 + 5;
int N, W[MAXN], L[MAXN], P[MAXN];
int sum[MAXN], F[MAXN], idx[MAXN];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> N;for (int i = 0; i < N; ++i)cin >> W[i] >> L[i] >> P[i];for (int i = 0; i < N; ++i)sum[i + 1] = sum[i] + W[i];for (int i = 0; i < N; ++i)F[i] = sum[i + 1] - L[i];iota(idx, idx + N, 0);sort(idx, idx + N, [&](const int i, const int j){ return F[i] < F[j]; });int cost = 1e9, id = -1;set<int> st;for (int i = 0, j = 0, s = 0; i < N; ++i){while (j < N && F[idx[j]] <= sum[i]){if (idx[j] >= i)s += P[idx[j]], st.insert(idx[j]);++j;}if (s < cost)cost = s, id = i;int k;while (st.size() && (k = *st.begin()) <= i)s -= P[k], st.erase(k);}for (int i = id; i < N; ++i)if (F[i] <= sum[id])cout << i + 1 << '\n';return 0;
}