【アルゴリズム】貪欲法

貪欲法というアルゴリズムがあります。英語だとGreedy Algorithmです。簡単に言うと、ある問題を部分的な問題に分解した上で、個々の問題に対して最適なケースを適用して、それを解とするアルゴリズムです。考え方が割とシンプルなので、ハマれば強力ですがそもそも貪欲法で求める解が得られるんだっけと言うところが判断しづらいです。

アットコーダーにて、貪欲法を適用する問題が出ました。

i番目の勇者が、i番目の街のモンスターを全力で倒す。倒して、余力があれば次の街のモンスターを倒す。と最適なケースを定めれば解ける問題です。以下のコードで解が求まりました。

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int N; cin >> N;
  vector<long> enemies;
  vector<long> heroes;
  for (int i=0; i<N+1; i++) {
    long A;cin>>A;
    enemies.push_back(A);
  }
  for (int i=0; i<N; i++) {
    long B;cin>>B;
    heroes.push_back(B);
  }

  long defeatTotalCount = 0;
  for (int i=0; i<N; i++) {
      long defeatCount = min(enemies[i], heroes[i]);
      long defeatCountOfNextCity = (heroes[i] > enemies[i]) 
      ? min(heroes[i] - enemies[i], enemies[i+1]) : 0;
      defeatTotalCount += defeatCount + defeatCountOfNextCity;
      enemies[i+1] -= defeatCountOfNextCity;
  }

  cout << defeatTotalCount << endl;
}