CF1712D

cachejtt · 2022-08-15 16:57:52 · 题解

题意

给你一个序列，你可以修改任意次，每次把序列中任意 k 个数修改为一个你自己选择的 x（x\le 10^9）。

构造一个完全图，若一条边连接 (i,j)，则边权为\min(a_i,a_{i+1},\dots,a_j)。请让图的直径最大。

图的直径定义为：任意两点间最短路的最大值。

思路

我们约定:

用 \operatorname{d}(u,v) 表示 u 与 v 的最短路。
用 \operatorname{e}(u,v) 表示连接 u 与 v 的边的边权。
用 diameter 表示图的直径。
用 minn 表示 \min(a_1,a_2,\dots,a_n)。

考虑以下事实。

显然对于这题，两点间最短路，最多经过两条边。则

\operatorname{d}(u,v)=\min(\operatorname{e}(u,v),2\times minn)

这是因为，两点间最短路，或直接到达，或走两条边。若直接到达，则值为

\operatorname{e}(u,v)=\min(a_u,\dots,a_v)

若走两条边，则一定是走两次边权最小的那种边，也就是说，假设 i_{min} 为 a_i 最小值的下标，则最短路大小为

\operatorname{e}(u,i_{min})+\operatorname{e}(i_{min},v)=2\times a_{i_{min}}

故得上式。

再看有关 \operatorname{e}(u,v) 的性质。

由于 \operatorname{e}(u,v)=\min(a_u,\dots,a_v)，故选择任意一个 p\ge v，有 \operatorname{e}(u,v)\ge \operatorname{e}(u,p)

故

\operatorname{e}(u,v) & = \min(\operatorname{e}(u,u+1),,\dots,\operatorname{e}(v-1,v)) \\ & = \min\limits_{u\le i\le v-1}(\operatorname{e}(a_i,a_{i+1})) \end{aligned}

可得

diameter & = \max({d(u,v)}) \\ & = \max{(\min(\operatorname{e}(u,v),2\times minn)}) \\ & = \min(2\times minn,\max(\operatorname{e}(u,v))) \\ & = \min(2\times minn,\max(\min\limits_{1\le i\le n-1}(a_i,a_{i+1}))) \end{aligned}

做法

我们已经推导过，

diameter= \min(2\times minn,\max(\min\limits_{1\le i\le n-1}(a_i,a_{i+1})))

接下来只需二分答案。

设当前答案为 ans，则将所有 \le \dfrac{ans}{2} 的点赋值成 10^9。为什么是 \dfrac{ans}{2} 呢？因为这条边若作为 minn 的话，会被走两次，也就是上面式子中的 2\times minn。

现在记录一下我们修改了几次，设为 cnt。

若 cnt>k，显然不可能
若 cnt=k，只需计算当前直径是否可行。若 diameter\le ans 则可行。
若 cnt<k，若 k>1，则一定可以有更多修改空间，即一定可以；若 k=1，否则因为只能修改一个，只需寻找 a_i 最大值并与 ans 比较即可。

代码

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define nrep(i, a, b) for (int i = (a); i >= (b); --i)
#define endl "\n"
using namespace std;
int t=1,n,k,a[100005],aa[100005],l,r,mid;
int calc(){
  int m1=min(aa[1],aa[2]);
  rep(i,1,n-1){
    m1=max(m1,min(aa[i],aa[i+1]));
  }
  int m2=aa[1];
  rep(i,1,n){
    m2=min(m2,aa[i]);
  }
  return min(m1,2*m2);
}
bool check(int ans){
  int sum=0;
  rep(i,1,n)aa[i]=a[i];
  rep(i,1,n){
    if(aa[i]<(ans+1)/2)sum++,aa[i]=1e9;
  }
  if(sum>k)return false;
  else if(sum==k){
    int d=calc();
    if(d>=ans)return true;
    else return false;
  }
  else{
    if(k==1){
      int mm=aa[1];
      rep(i,1,n)mm=max(mm,aa[i]);
      if(mm>=ans)return true;
      else return false;
    }
    else return true;
  }
}
signed main(){
  ios::sync_with_stdio(0);
  cin>>t;
  rep(kk,1,t){
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    l=1;
    r=1e9;
    while(l<r){
      mid=(l+r)>>1;
      if(check(mid))l=mid+1;
      else r=mid;
    }
    while(check(l) && l<n)l++;
    while(check(l)==0 && l>1)l--;
    cout<<l<<endl;
  }
  return 0;
}