AtCoder Beginner Contest 135 C - City Savers(300点)

long long int にしていなくて２回くらいWAになった。(フザケンナ）

WAになって頭真っ白になってもう一回考察し直したのは良い思い出( ＾∀＾)

問題へのリンク

問題概要

N+1の街があり、それぞれの街にはモンスターがAi体います。

N人の勇者が居て、勇者はi,i+1の街のモンスターを討伐することが出来ます。

勇者が倒せるモンスターは最大で何体でしょう。

制約

• 入力は全て整数である。
• $1\le N\le {10}^5$
• $1\le A_i\le {10}^9$
• $1\le B_i\le {10}^9$

解法

街で見るのではなく勇者で見ることにした。

つまり、n回のループで勇者の値であると街の，を見るようにしている。

さて、この考え方ではa[i]>=b[i]とそうでない時の場合分けが必要となる。

(1)a[i]>=b[i]の時

勇者が最大の力を出すことが出来るのでans+=b[i]をする

(2)そうでない時

勇者の力が有り余ってるのでとりあえずans+=a[i]をしてを見てあげる。そうした時最初のように場合分けをすれば良い

#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;

int main(){
  Int n;cin >> n;
  Int ans=0;
  vector<Int> a(n+1),b(n);
  for(auto &i:a) cin >> i;
  for(auto &i:b) cin >> i;
  for(Int i=0;i<n;i++){
    if(a[i]>=b[i]){ans+=b[i];}
    else{
      ans+=a[i];
      b[i]-=a[i];
      if(a[i+1]>=b[i]){a[i+1]-=b[i];ans+=b[i];}
      else{ans+=a[i+1];a[i+1]=0;}
    }
  }
  cout << ans << endl;
}