Codeforces Round #813 (Div. 2) - D. Empty Graph

构造

Problem - D - Codeforces

题意

给 \(n(1<=n<=10^5)\) 个点，与权值 \(a_i\)，这 \(n\) 个点组成一个完全图，\(a_l\) 与 \(a_r\) 连的边的权值为 \(min(a_l,a_{l+1}...a_{r-1},a_r)\)

有 \(k\) 次机会可以把任意一个点的权值变为 INF，求 k 次操作后这个图的直径的最大值

图的直径为任意两个点的最短路中，最长的那一条

思路

1. 对于两个点 \(l,r\) 的最短路，要么直接从 l 走到 r，为 \([l,r]\) 的最小值；要么 l 到权值最小的点 t 再到 r，为 \(2*a_t\)

   因此直径只可能在 \(a_i,a_{i+1}\) 取到

2. 直径有两种情况得到，一种是在最大的 \(min(a_i,a_{i+1})\) 取到；一种是在 2 倍最小权值取到

   1. 希望在 \(min(a_i,a_{i+1})\) 取到

   可以先花 k - 1 次让前 k - 1 小的权值变成 INF，留 1 次是因为可能操作 k - 1 次后所有 INF 的位置都是不相邻的，\(min(a_i,a_{i+1})\) 取不到 INF，最后一次让某一项 INF 旁边的变成 INF，这样最大的 \(min(a_i,a_{i+1})\) 就可以取到 INF了；再与 2 倍最小权值取 min

   2. 希望在 2 倍最小权值取到

      直接花 k 次让最小的 k 个权值都变成 INF，再枚举 \(min(a_i,a_{i+1 })\), 求出 2 倍最小权值与最大的 \(min(a_i,a_{i+1 })\) 的最小值

   两者取 max 即为答案

​ 思路 2 比思路 1 优在最小权值更大，但可能最大的 \(min(a_i,a_{i+1})\) 不够大

​ 思路 1 比思路 2 优在最大的 \(min(a_i,a_{i+1})\) 达到了 INF，可以不用考虑这条路了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
const int INF = 1e9;
struct Node
{
	int val, id;
	bool operator<(const Node &x) const
	{
		return val < x.val;
	}
}b[N];
int a[N];
int n, k;

int solve()
{
	for (int i = 1; i <= n; i++)
		b[i] = {a[i], i};
	sort(b + 1, b + n + 1);
	for (int i = 1; i < k; i++)
	{
		b[i].val = INF;
		a[b[i].id] = INF;
	}
	sort(b + 1, b + n + 1);
	int ans, ans1 = INF, ans2 = INF;
	ans1 = min(b[1].val * 2, b[n].val);

	b[1].val = INF;
	a[b[1].id] = INF;
	sort(b + 1, b + n + 1);
	ans2 = min(ans2, b[1].val * 2);
	for (int i = 1; i <= n; i++)
		a[b[i].id] = b[i].val;
	int tmp = -INF;
	for (int i = 1; i < n; i++)
		tmp = max(tmp, min(a[i], a[i+1]));
	ans2 = min(ans2, tmp);
	ans = max(ans1, ans2);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		cout << solve() << endl;
	}
    return 0;
}