AGC009: A - Multiple Array

問題

A - Multiple Array

解説

押した場所とその左側が全て1増加するので、必要最小限を考えるなら右から貪欲する。 類題沢山ある気がするしパターン化できそう？

コード

int N;
int a[100010];
int b[100010];

int main() {
  cin >> N;
  rep(i, N) cin >> a[i] >> b[i];
  int64_t plus = 0;
  rep(i, N) {
    int k = N - i - 1;
    int po = b[k] - (a[k] + plus) % b[k];
    if (po < b[k]) {
      plus += po;
    }
  }
  cout << plus << "\n";
}