D. Empty Graph #813 div2

Graph #813 div2"/>

D. Empty Graph #813 div2

Problem - D - Codeforces

题意是给你一组序列，编号1，2，3对应着点的编号，根据这个序列创建一个无向有权图。然后从点a到点b的权值就是对应在这个序列里面的[a,b]的最小值，然后找到所有从一个点到另外的一个点的最短路的权值最大。

可以有不超过k次的操作：选择一个任意索引，使得a[i]=x（x∈[1,1e9]）

贪心 二分都可以写

下面我说贪心的思路

这题你要从图里面发现很多性质才可以把这个题写掉

首先：图的最大权值必然是相邻的点的最小值，即min(a[i],a[i+1])

证明：点al到ar的权值为[l,r]的最小权值，你在一个数组里面有个值最小，因为有这个值的存在，包含这个点的所有区间对应到所有的点的权值都是那个最小的数，为了方便起见，这个值也就是相邻的点的权值，整体上来看最大的权值必然是某个相邻的点的权值

第二：这个题的本质是从a到b的最短路的最大值

a到b可以有两种走法：这里定义一个最小值ax（在x的位置上）

①：a->b，这种情况在区间[a,b]上面没有这个ax，也就是没有整体的这一个最小值。就是a直接到b，这个遍历一遍就好，取路上的最小权值然后取max

②：a->x->b，在这一段路径上包含了ax，也就是最小值在这个区间上面，那这个a到b的权值也就是先可以a到x，然后x到b，所以这种情况的权值就是ax*2

好，上面是两种可能的走法，如果k==0，那上面的就是答案了。

现在开始使用k，就开始依据上面然后基于贪心的思想，开始进行最小值的最大化

根据上面的第一种情况的表达式:maxn=max(maxn,min(a[i],a[i+1])

第二种情况是尽可能的把最小值变大，然后ax*2

一个是线性一个是平方，所以首选的是第二种：让最小值尽可能的变大

怎么变大？就是把前k-1小的数变成正无穷，然后第k个数理应就是变化后的最小值

刚刚说到前k-1小的数，把k-1次都留在操作最小值，然后第k次有两种选择：

要么是继续操作最小值，要么是增加a->b，这里操作一次，也就是增加一次即可（第一种操作），多了没意义，反正都是取两者的最小值。就是取两者种的最小值，无论怎么变化，我们都可以把其中一个权值变成无穷大，然后取最大权值的那个就好

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e9,mod=1e9+7;
int a[N],b[N];
signed main(){//IOS;int T;//T=1;cin>>T;while(T--){	priority_queue<PAII,vector<PAII>,greater<PAII>> q;int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];q.push({a[i],i});}for(int i=1;i<=k-1;i++)//这里操作k-1次 {auto t=q.top();q.pop();int pos=t.second;q.push({INF,pos});a[pos]=INF;}for(int i=1;i<=n;i++) b[i]=a[i];//b数组留最后一次操作过程量 auto t=q.top();q.pop();int p1=t.second;q.push({INF,p1});a[p1]=INF;//a数组继续操作最小值 int maxn=-1e18;for(int i=1;i<=n-1;i++) maxn=max(maxn,min(a[i],a[i+1]));sort(a+1,a+n+1);int res1=min(a[1]*2,maxn);sort(b+1,b+n+1);int res2=min(b[1]*2,b[n]);//这里b是把其中的一个变大，不管怎么样都是可以取到最大权值，所以这里不用具体实现增加过程量，直接是最大权值就好，也就是b[n] cout<<max(res1,res2)<<"\n";}return 0;
}
/**/