AtCoder Beginner Contest 116 C Grand Garden
問題
問題概要
全てを に初期化された数列のうち, ある区間を選んで ずつ増やしていく。
この数列を数列 と等しくするには何回操作を行う必要があるか。
考察
数列 のうち最大の要素を とします。
また, 要素数が と等しい, 全てが0で初期化された配列 を用意します。
一回の操作では各要素を しか増やせないため から まで, と と比較しつつ, 操作をシミュレーションすれば良いです。
提出コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n; cin >> n; vector<ll> h(n); // 数列hの最大値, 最小値 ll mmin = 1000, mmax = -1; rep(i,n) { cin >> h[i]; mmin = min(h[i],mmin); mmax = max(h[i],mmax); } ll ans = mmin; // 数列tは最小値で初期化しておく(最小値回, 区間(0,n-1)に水をかけることは確定している) vector<ll> t(n,mmin); for (int i = mmin; i <= mmax; ++i) { // 1つ前の要素を増加させているかを判断するフラグ bool flag = false; for (int j = 0; j < n; ++j) { if (t[j] < h[j] and !flag) { // フラグが立っていなければ, 要素jが区間の左端になる flag = true; // 実際に配列tもインクリメントして操作をシミュレート t[j] += 1; } else { if (flag) { // フラグが立っていればこの1つ前の要素が区間の右端 ans += 1; // フラグを折っておく flag = false; } } } // 右端を見た後にフラグが立っていれば, 要素n-1が区間の右端だったことがわかる if (flag) { ans += 1; } } cout << ans << endl; }