2022icpc亚洲区域赛（南京站）Problem D - 聊天程序
发布时间
阅读量：
阅读量
\Huge{2022icpc亚洲区域赛（南京站）Problem D - 聊天程序}
文章目录
- 题意
- 思路
- 标程
官方题解：D - 聊天程序 - SUA Wiki
题意
本题首先给出n,k,m,c,d，然后给出n个整数a_1,a_2...a_n。
题目要求执行以下操作至少一次：
从给定数组中选取长度为m的一个连续子序列a；接着按照顺序将其与首项为c、公差为d的一个等差数列进行叠加。
求至多一次操作之后，序列中第k大的值最大可能是多少？
数据范围：
- 1\le k,m\le n \le 2\times 10^5
- 0\le c,d \le 10^9
- 0\le a_i\le 10^9
思路
根据题目的意思我们可以得出结论我们需要确定的答案具有单调性特征具体来说如果答案k满足条件那么所有比k小的数值同样满足这一条件但需要注意的是在此前提下我们无需考虑是否能够构造出k
因此，我们考虑使用二分答案。
当我们使用二分查找法进行枚举时，在判断所有小于k的情况时（即当k是我们要找的最大满足条件的那个值），函数check()必然返回真值。因此确定存在这样的特定值k使得构造成功。
然而，这道题目的主要难点在于这一过程的判断逻辑，并且必须维持这一时间复杂度水平，并且可以通过这种方法来解决。
具体做法为：
- 首先我们采用二分查找的方式确定阈值mid并将所有大于等于mid的数值标记为1其余标记为0这样我们的目标转化为判断是否存在一种最多一次的操作使得序列中标记为1的数值数量至少达到mid个。
- 接着我们遍历所有可能的操作区间并计算执行该操作后的结果是否满足条件考虑到一个元素a_t(a_t < x)我们可以观察到当其首次进入当前的操作区间时会成为该区间内的最大值随后随着区间的右端不断扩展这个最大值逐渐减小直至区间的右端到达a_t的位置后又恢复到原来的数值因此每个元素最多只会经历两次状态转换：从0变为1一次并在达到最大值后又由1变为0一次。
- 对于每一个元素来说在其状态发生两次转变时（即由0变1再到0）我们需要确定这两个转变的具体位置并利用前缀和的方法来评估在这些位置上执行操作如何影响序列中1的数量。
标程
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long
#define ULL unsigned long long
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
const int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, k, m, c, d;
vector<int> a, f;
bool check(int mid) {
int cnt = 0;//记录不小于mid的个数
for(int i = 1; i <= n; i ++ ) if(a[i] >= mid) cnt ++;
if(cnt >= k) return true;//剪枝，个数符合直接范围true
f.clear(); f.resize(n + 5); //关键的f数组，用于记录前缀和
for(int i = 1; i <= n; i ++ ) {
if(a[i] >= mid) continue; //只判断小于mid的数字
int r = min(m - 1, i - 1);
int mx = a[i] + c + d * r; //当前数字最大能加多少
if(mx < mid) continue;
f[max(m, i)] ++; //记录这个数字大于mid的区间的起点的坐标
int mi = a[i] + c; //当前数字最小能加多少
if(mi >= mid) f[min(i + m, n + 1)] --;//若加最小也满足，则只有其不在区间m中时才去掉
else {
int t = mid - a[i] - c;
int pos = (t + d - 1) / d - 1;
f[min(n + 1, i + m - pos - 1)] --;
}
}
for(int i = m; i <= n; i ++ ) {
cnt += f[i];
if(cnt >= k) return true;
}
return false;
}
void Solved() {
cin >> n >> k >> m >> c >> d;
a.resize(n + 1);
for(int i = 1; i <= n; i ++ ) {
cin >> a[i];
}
int l = 0, r = 1e15, mid;//需要根据题目计算出答案可能的最大值
while(l < r) {
mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
signed main(void) {
IOS
int ALL = 1;
// cin >> ALL;
while(ALL -- ) Solved();
// cout << fixed;//强制以小数形式显示
// cout << setprecision(n); //保留n位小数
return 0;
}
cpp
全部评论 (0)
还没有任何评论哟~