题解：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:

CPP

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

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

文章操作

观察题目

处理

考虑优化

AC code:

相关推荐

评论

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