C - City Savers

はじめに

たなしょです。

難しかったです。貪欲法を使うらしいです。

今回はこちらのブログの記事を参考にさせていただきました。

問題文

https://atcoder.jp/contests/abc135/tasks/abc135_c

いざ実装

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>

typedef long long ll;

using namespace std;

int main() {
  int N;
  cin >> N;
  ll A[N], B[N];
  for (int i = 0; i <= N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  ll s = 0;
  for (int i = 0; i < N; i++) {
    s += min(A[i], B[i]);
    B[i] -= min(A[i], B[i]);
    A[i] -= min(A[i], B[i]);
    s += min(A[i + 1], B[i]);
    A[i+1] -= min(A[i + 1], B[i]);
  }
  cout << s << endl;
  return 0;
}

考え方

  int N;
  cin >> N;
  ll A[N], B[N];
  for (int i = 0; i <= N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  ll s = 0;

long long型で配列を宣言しています。（long long型はtypedefでllという型名にしています）

その後はfor文を回して各配列に値を代入しています。

今回は配列の中身は

1. A = [3, 5, 2]
2. B = [4, 5]

とします

s += min(A[i], B[i]);

これはs = min(3, 4)になります。

min関数は2値の最小値を取得するのでsに3を足します

B[i] -= min(A[i], B[i]);

B[0] = 4なのでその値にmin(3, 4)で算出される値を引けば良いので、

B[0] = 4 - 3 = 1になりB[0] = 1が求まります。

A[i] -= min(A[i], B[i]);

A[0] = 3でその値をmin(3, 1)で算出される値で引けば良いので（一つ前の計算でB[0]は1になっています。）

A[0] = 3 - 1 = 2が求まります。

s += min(A[i + 1], B[i]);

sにmin(A[1], B[0])で算出される値を足します。

min(A[1], B[0])はmin(5, 1) になるので1が求まります。

s = 3 + 1 = 4が求まります。

A[i+1] -= min(A[i + 1], B[i]);

A[1] = 5 にmin(5, 1)か算出された値を引けば良いので

A[1] = 5 - 1 = 4になります。

上記をN-1回繰り返してsの値を出力すれば完了です。

最後に

貪欲法。まだまだ知らないことばかりです。

日々精進ですね。

最後まで読んでいただいてありがとうございました。 もしよろしければtwitterアカウント（@piklus100yen）もフォローしていただけると幸いです！