SRM683 D2M MoveStonesEasy

TopCoder Statistics - Problem Statement

There are n piles of stones arranged in a line. The piles are numbered 0 through n-1, in order. In other words, for each valid i, piles i and i+1 are adjacent. You are given two int[]s a and b, each with n elements.

現在の石の山と目的の石の山が渡されるので，左から順番に目的の石の山にしていく．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public:
int get(vector <int> a, vector <int> b) {
  int n = a.size();

  ll ans = 0;
  ll asum = 0, bsum = 0;

  rep(i, n) asum += a[i];
  rep(i, n) bsum += b[i];

  if(asum != bsum) return -1;

  rep(i, n) {
      if(a[i] == b[i]) continue;
      if(a[i] > b[i]) {
          a[i+1] += a[i] - b[i];
          ans += a[i] - b[i];
      } else {
          int len = 1, j = i+1;
          while(a[i] < b[i]) {
              int d = b[i] - a[i];
              if(a[j] >= d) {
                  a[j] -= d;
                  a[i] += d;
                  ans += d * len;
              } else {
                  a[i] += a[j];
                  ans += a[j] * len;
                  a[j] = 0;
                  j++;
                  len++;
              }
          }
      }
  }

  return ans;
}
Mar 3rd, 2016
srm, topcoder, シュミレーション