A - Addition Range Queries

問題

https://codeforces.com/gym/103150/problem/A (新しいタブで開く)

問題文

長さ $n$ の数列が与えられる。その数列に対して、以下の操作を $k$ 回行う。

各要素を、ほかのすべての要素の合計で置き換える。具体的には、次のすべてが 同時に 起きる。
それぞれの $i$ について、 $a_i$ を $a_1 + a_2 + \cdots + a_{i-1} + a_{i+1} + \cdots + a_n$ で置き換える。

最終的な数列の 差の最大値 を求める。

制約

• テストケース数: $1 \le t \le 10^4$
• $1 \le n \le 10^5$
• $1 \le k \le 10^9$
• $1 \le a_i \le 10^9$
• $n$ の総和は $2 \times 10^5$ を超えない

サンプル

3
4 1
1 3 5 4
1 1000
2020
10 100000
1 1 1 1 1 1 1 1 1 1

4
0
0

考察

1 回操作を行うと、 $s = \sum a_i$ として、 $\left[ s - a_1, s - a_2, \cdots, s - a_n \right]$ になる。
このとき、最大の差は $|\max(s - a_i) - \min(s - a_i)| = |\min(a_i) - \max(a_i)| = |\max(a_i) - \min(a_i)|$ になる。
これを何回やっても変わらないので、結局答えは最初の数列の差の最大値。

コード

https://codeforces.com/gym/103150/submission/120702811 (新しいタブで開く)

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  int maxim = *max_element(a.begin(), a.end());
  int minim = *min_element(a.begin(), a.end());
  cout << maxim - minim << endl;
  return;
}