A - Addition Range Queries
cpcodeforcesmathdiv2
最終更新日
問題
https://codeforces.com/gym/103150/problem/A
問題文
長さ n の数列が与えられる。その数列に対して、以下の操作を k 回行う。
各要素を、ほかのすべての要素の合計で置き換える。具体的には、次のすべてが 同時に 起きる。
それぞれの i について、 ai を a1+a2+⋯+ai−1+ai+1+⋯+an で置き換える。
最終的な数列の 差の最大値 を求める。
制約
- テストケース数: 1≤t≤104
- 1≤n≤105
- 1≤k≤109
- 1≤ai≤109
- n の総和は 2×105 を超えない
サンプル
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=∑ai として、 [s−a1,s−a2,⋯,s−an] になる。
このとき、最大の差は ∣max(s−ai)−min(s−ai)∣=∣min(ai)−max(ai)∣=∣max(ai)−min(ai)∣ になる。
これを何回やっても変わらないので、結局答えは最初の数列の差の最大値。
コード
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;
}