2022icpc亚洲区域赛（南京站）Problem D

2022icpc亚洲区域赛（南京站）Problem D - 聊天程序

本文主要是介绍2022icpc亚洲区域赛（南京站）Problem D - 聊天程序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\Huge{2022icpc亚洲区域赛（南京站）Problem D - 聊天程序}$

文章目录

题意
思路
标程

题目链接：Problem - D - Codeforces

官方题解：D - 聊天程序 - SUA Wiki

题意

本题首先给出 $n, k, m, c, d$ ，然后给出 $n$ 个整数 $a_1,a_2...a_n$ 。

题目要求执行以下操作至少一次：

选择一个长度恰好为 $m$ 的子数组 $a$ ，然后将长度也为 $m$ 的等差数组（首项为 $c$ ，公差为 $d$ ）依次加到对应的子数组 $a$ 上。

求至多一次操作之后，序列中第 $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()函数必然是返回true，所以说使用二分答案最终枚举到的 $k$ 必定可以构造出。

但是，这道题目的难点就在于check()函数的判断，check()函数的时间复杂度必须保持在 $O (n)$ 的时间复杂度下可通过本题。

具体做法为：

首先二分答案 $mi d$ ，将大于等于 $mi d$ 的数看成 $1$ ，小于 $mi d$ 的数看成 $0$ 。问题变为“判断能否通过至多一次操作，使序列中 $1$ 的数量大于等于 $mi d$ ”。
接下来枚举操作位置，并计算进行操作后能否满足要求。考虑一个元素 $a_t(a_t<x)$ 容易发现，在操作范围从左往右移的过程中，当 $a_t$ 第一次进入操作范围时，它会变成最大值，之后慢慢变小，最后又变回原来的值。因此每个数只会从 $0$ 变成 $1$ 一次，再从 $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 secondconst 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;//剪枝，个数符合直接范围truef.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) {IOSint ALL = 1; // cin >> ALL;while(ALL -- ) Solved();// cout << fixed;//强制以小数形式显示// cout << setprecision(n); //保留n位小数return 0;
}