[Codeforces] Codeforces Round #668 (Div. 2) B. Array Cancellation
問題
方針
\( i < j \) のとき、\( a_i \leftarrow a_i – 1 \)、\( a_j \leftarrow a_j + 1\) という操作は \( 0 \) コストでできますが、\( i > j \) ではコストが \( 1 \) かかります。
前から順番に調べていき、\( a_i > 0 \) となる \( a_i \) の和を \( s \) とします。\( s \) が正であれば、\( a_i < 0 \) となる要素にたいして \( s \) までコストが掛からずに操作を行うことができます。
\( a_i < 0 \) のとき
\( a_i + s \geq 0 \) ならばノーコストで \( a_i = 0 \) とすることができます。また、\( s \leftarrow a_i + s \) と更新します。\( a_i + s < 0 \) のとき、\( -(a_i + s)\) のコストを払い \( a_i = 0 \) とすることができます。また、\( s = 0 \) となります。
\( a_i \geq 0 \) のとき
\( s \leftarrow a_i + s \) と更新します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[100000]{}; ll solve(int n) { ll ret = 0; ll sum = 0; for (int i = 0; i < n; i++) { if (a[i] <= 0) { if (sum + a[i] >= 0) { sum += a[i]; } else { ret += -a[i] - sum; sum = 0; } } else { sum += a[i]; } } return ret; } int main() { int t, n; cin >> t; ll ans[t]{}; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { cin >> a[j]; } ans[i] = solve(n); } for (ll i : ans) { cout << i << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません