A - Addition Range Queries

cpcodeforcesmathdiv2

最終更新日

Table of Contents

Loading...

問題

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 で置き換える。

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

制約

サンプル

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; }