构造
题意
给 \(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 次操作后这个图的直径的最大值
图的直径为任意两个点的最短路中,最长的那一条
思路
-
对于两个点 \(l,r\) 的最短路,要么直接从 l 走到 r,为 \([l,r]\) 的最小值;要么 l 到权值最小的点 t 再到 r,为 \(2*a_t\)
因此直径只可能在 \(a_i,a_{i+1}\) 取到
-
直径有两种情况得到,一种是在最大的 \(min(a_i,a_{i+1})\) 取到;一种是在 2 倍最小权值取到
- 希望在 \(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 倍最小权值取到
直接花 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;
}
标签:min,int,Graph,Codeforces,最小,权值,INF,include,Div
From: https://www.cnblogs.com/hzy717zsy/p/16717673.html