题意 给定一个长度为 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;
}
这是本题本人代码,各路大佬帮我看看是否正确,谢谢