CF1712D 题解
sunkuangzheng
·
2023-10-03 10:19:35
·
题解
\textbf{1.1 Describtion}
给定长度为 n 的序列 a 和一张无向完全图，边 u,v(u \le v) 的权值是 \min\limits_{i=u}^v\{a_i\} 。你可以进行 k 次操作，让 a_i \gets x,x \in [1,10^9] 且 x 的值由你选定，问操作完后图的直径的最大值。图的直径即最大的两点之间的最短距离。
$\textbf{1.2 Hints}
设 d(u,v) 表示 u 到 v 的最短路，尝试确定 d(u,v) 的上界。
尝试证明 d(u,v) = \min(\min\limits_{i=u}^v\{a_i\},2\min\limits_{i=1}^n\{a_i\}) 。
根据 \text{Hint 2} 中的结论，为了让 d(u,v) 最大，选取的 u,v 应该满足什么关系？
二分答案。
\textbf{1.3 Solution}
我们先对 \text{Hint 2} 中的结论做简要证明。
设 1 \sim n 中 a_i 取最小值的地方是 i = p ，那么由于完全图，显然存在路径 u \to p \to v ，路径长度是 2a_p ，又因为可以直接走边 u,v ，所以d(u,v) = \min(\min\limits_{i=u}^v\{a_i\},2\min\limits_{i=1}^n\{a_i\}) 。
我们二分答案 $x$，贪心的检验答案。很容易发现每次都让 $a_i \gets 10^9$ 一定不劣。首先如果不能在 $k$ 次操作内让最小值的 $2$ 倍 $\ge x$，肯定不合法。设 $k_1$ 是已经操作过的次数，$k_2$ 是剩余的次数，那么如果 $k_2 \ge 2$ 肯定合法。如果存在一个 $i \in [1,n-1]$ 满足 $\min(a_i,a_{i+1}) \ge x$，或者 $\max(a_i,a_{i+1}) \ge x$ 并且 $k_2 \ge 1$，也是合法情况。
上面的检验是线性的，所以时间复杂度 $\mathcal O(n \log V)$。
**【代码】**
```cpp
/**
* author: sunkuangzheng
* created: 03.10.2023 09:41:34
**/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int t,n,k,a[maxn],b[maxn],c[maxn],d[maxn];
bool cmp(int x,int y){return a[x] < a[y];}
bool ck(int x){
int lk = 0;
for(int i = 1;i <= n;i ++) a[i] = b[i];
for(int i = 1;i <= n;i ++) if(a[i] * 2 < x) lk ++,a[i] = 1e9;
if(lk > k) return 0;if(k - lk >= 2) return 1;
for(int i = 1;i < n;i ++) if(min(a[i],a[i+1]) >= x) return 1;
else if(max(a[i],a[i+1]) >= x && lk != k) return 1;
return 0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> t;
while(t --){
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> a[i],b[i] = a[i],c[i] = i;
int l = 1,r = 1e9;
while(l <= r){
int mid = (l + r) / 2;
if(ck(mid)) l = mid + 1; else r = mid - 1;
}cout << l - 1 << "\n";
}
}
```