CF Round #840-C.Another Array Problem
描述
给定一个包含\(n\)个元素的序列\(a\), 可以进行以下操作任意次:
选择下标\(i, j(1<=i<j<=n)\), 将所有\(a_k\)替换为\(|a_i-a_j|(i<=k<=j)\).
问序列能操作出的最大元素和.
思路
n>=4
对于\(n>=4\)时, 可以发现这样的一个特点:
对于任意相邻两元素, 做两次这种操作可使这两个元素都变为0.
以\(n=4\)为例:
1 3 4 7 -> 2 2 4 7 -> 0 0 4 7
1 3 7 4 -> 2 2 7 4 -> 0 0 7 4 -> 7 7 7 4 -> 7 3 3 3 -> 7 0 0 0 -> 7 7 7 7
当最大元素位于其他位置同理.
n=3
设各元素分别为\(a, b, c\)
有几种小情况:
-
\(a\)最大, 那么答案可以取到\(3a\).
-
\(c\)最大, 那么答案可以取到\(3c\).
-
\(b\)最大, 那么答案可以取到\(max\{a+b+c, 3*(b-a), 3*(b - c)\}\).
n<=2
比较简单
代码
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int &i : a) {
cin >> i;
}
if (n >= 4) {
cout << n * *max_element(a.begin(), a.end()) << '\n';
} else if (n == 2) {
cout << max({a[0] + a[1], (a[0] - a[1]) * 2, (a[1] - a[0]) * 2}) << '\n';
} else if (n == 3) {
int ans = a[0] + a[1] + a[2];
ans = max({ans, 3 * a[0], 3 * a[2]});
if (a[1] > a[0]) {
ans = max(ans, 3 * (a[1] - a[0]));
}
if (a[1] > a[2]) {
ans = max(ans, 3 * (a[1] - a[2]));
}
cout << ans << '\n';
} else if (n == 1) {
cout << a[0] << '\n';
}
}
标签:思维,cout,int,max,每日,元素,cin,ans,一题
From: https://www.cnblogs.com/whose-dream/p/17004686.html