EZ Programming Contest #1 - A. Addition Range Queries


Tags:cpcodeforcesmath

問題

https://codeforces.com/gym/103150/problem/A

問題文

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

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

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

制約

  • テストケース数: 1t1041 \le t \le 10^4
  • 1n1051 \le n \le 10^5
  • 1k1091 \le k \le 10^9
  • 1ai1091 \le a_i \le 10^9
  • nn の総和は 2×1052 \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=ais = \sum a_i として、 [sa1,sa2,,san]\left[ s - a_1, s - a_2, \cdots, s - a_n \right] になる。
このとき、最大の差は max(sai)min(sai)=min(ai)max(ai)=max(ai)min(ai)|\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;
}