题解：P14306 【MX-J27-T3】旋律

· · 题解

观察题目

题目求一段序列的长度乘 k 减去极差的最大值。

因为不是子串，所以跟元素的位置没有关系。

处理

我们将题目 a 升序排序，可以证明最后取得的答案实际上是排序后序列的子串，最大值就是右端点元素，最小值就是左端点元素，极差就是右端点的元素减去左端点的元素。

那么所求即为：

\max\limits_{i = 1}^{n}((j - i + 1) \times k- (a_j - a_i))) (i < j \le n)

此时复杂度 O(n^{2})。

考虑优化

计算每一位的贡献，发现如果当前已经得到了一个答案，现在加入下一位，那么序列长度加 1, 极差加 a_i - a_{i - 1}，因此对答案的贡献为 k - (a_i - a_{i - 1})。

于是我们可以预处理出每一位的贡献（第 2\sim n 位），即为序列 w，发现我们只需要求 w 的最大子段和即可。注意一下细节，第一位还有 1 的长度，所以最后答案要加 k。

AC code:

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; i ++)
using namespace std;
const int N = 1e5 + 10;
int a[N], w[N], f[N];
void solve() {
    int n, k; cin >> n >> k;
    int ans = 0;
    REP(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);
    REP(i, 1, n) w[i] = k - (a[i] - a[i - 1]);
    REP(i, 2, n) f[i] = max(f[i - 1] + w[i], w[i]), ans = max(ans, f[i]);
    cout << ans + k << '\n';
}
signed main(){
//  File("melody");
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int c, T; cin >> c >> T;
    while (T --) solve();
    return 0; 
}