🎃
Tenka1 Programmer Beginner Contest | C - Align
問題
考えたこと
最適な解の数列をBとし、i番目の数値を
このとき数列に、
もし存在するとしたら、
最適な形としては以下の2パターンになる。
ここで、(1)のとき、
末尾は奇数か偶数かで変わってくるが、
ここで先程の
(2)のときも同じようにして解き、(1)と(2)の最大値を求めれば答えとなる。
コード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;
ll solve(vector<ll> &a, ll b0, ll b1) {
const int n = a.size();
vector<ll> b(n);
// p1 > p2 < p3 > p4 ...
b[0] = b0, b[1] = b1;
for (int i = 1; i < n - 1; i++) {
if (b[i] == -1) {
b[i] = -2;
b[i + 1] = 1;
} else {
b[i] = 2;
b[i + 1] = -1;
}
}
sort(b.begin(), b.end());
ll v = 0;
for (int i = 0; i < n; i++) {
v += a[i] * b[i];
}
return v;
}
int main() {
ll n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
// 係数を計算する
vector<ll> b(n);
ll mx = 0;
// p1 > p2 < p3 > p4 ...
mx = max(mx, solve(a, 1, -1));
// p1 < p2 > p3 < p4...
mx = max(mx, solve(a, -1, 1));
cout << mx << endl;
}
参考
Discussion