求助帖
  • 板块灌水区
  • 楼主Beta_Theta
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/24 14:31
  • 上次更新2023/11/2 18:20:00
查看原帖
求助帖
965461
Beta_Theta楼主2023/9/24 14:31

题意 给定一个长度为 n 的整数序列 a1,a2,..,an,同时给定另外四个整数 km,c,d。 小 L 可以进行以下操作至多一次:选择一个长度恰为m  的连续子数组,并将一个长度为 m ,首项为 c ,公差为 d 的等差数列加到该连续子数组上。 如序列是 3,1,4,1,5,将一个长度为 m=3,首项为 c=2,公差为 d=1 的等差子序列,加到序列中 a2,a3,a4 这个长度为 3 的连续子数组上,则序列变成 3,3,7,5,5。 小 L 希望最大化序列中第 k 大的值。 输入格式 第一行输入五个整数 n,k,m,c,d ,含义如题目所示。 第二行输入 n 个数,第 i 个数为 ai 。 输出格式 一行一个整数,表示序列中第 k大的值的最大值。 样例1 输入 8 3 5 0 0 2 0 2 2 1 2 1 8 输出 2 数据范围 对于 20% 的数据,保证 1≤k,,m≤n≤10。 对于另外 20% 的数据,保证 1≤k,m≤n≤1000。 对于另外 30% 的数据,保证 k=1。 对于 100% 的数据,保证 1≤k,m≤n≤2×100000,0≤c,d≤1000000000,0≤ai≤10000。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(vector<ll>& a, int k, int m, int c, int d, ll t) {
	ll n = a.size(), mid = 1 + (n - m) / 2,f = a[mid] - (mid - 1) * d,sum = 0, cnt = 0;
	for (int i = mid; i < mid + m; i++) sum += f + (i - mid) * d;
	for (int i = 0; i < n && cnt < k; i++) {
		if (i >= mid && i < mid + m) continue;
		if (a[i] + c <= sum || (a[i] == sum && i < mid)) cnt++;
	}
	return cnt >= k;
}
int main() {
	int n, k, m, c, d;
	cin >> n >> k >> m >> c >> d;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int l = 0, r = n - m;
	ll ans = 0;
	while (l <= r) {
		ll mid = l + (r - l) / 2, t = a[mid] + c;
		if (check(a, k, m, c, d, t)) {
			ans = t;
			l = mid + 1;
		} else r = mid - 1;
	}
	cout << ans;
	return 0;
}

这是本题本人代码,各路大佬帮我看看是否正确,谢谢

2023/9/24 14:31
加载中...