跳转至

Empty Graph

原题链接

题意

给定一长度为 \(n\) 的数组，你可以进行 \(k\) 次操作任意改变数组的一个值 \([1,10^9]\)，用该数组构建一张无向稠密图，对于任意 \([l, r]\) 两点之间的路径长度为数组 \(a\) 上 \([l, r]\) 范围内的最小值。求操作后该图上两个点之间最短路的最大值。

⭐rating: 2000

分析

图的性质

因为建图所得到的图为无向完全图，最短路有两种取得的方式，一种为直接从 \(u\) 走到 \(v\)，所需代价为 \(\min_{u\le i\le v}(a_i)\)；另一种是 \(u\) 先走到权值最小的点，再从最小的点走到 \(v\)，代价为 \(2\times\min_{1\le i\le n}(a_i)\)。

结论

最短路的最大值一定出现在两个相邻的位置上。

证明

我们发现如果两个位置不相邻并取到最大值，按照上述情况，他们经过最小权值的点，会发现如果把两个点变成相邻的话一定不会更差。如果最大值是从 \(u\) 直接走到 \(v\) 得到的，那么把 \(u\) 和 \(v\) 相互靠近，能够取到点更少，最小值一定大于等于刚才的距离。因此让两个最短路最长的点靠在一起不会让结果变坏。

情况①：最大值来自 u 直接走到 v

根据分析的结果，答案为 \(\min(a_i,a_{i+1})\)，那么之间必然存在一个最小值。所以我们需要用一次操作把其中小的那个变为无穷大，这样可以最终取到相对大的数。剩余的 \(k-1\) 次，将最小的 \(k-1\) 个数设置成无穷大即可。最终答案在最小值*2和最大值间取小值即可。

情况②：最大值来自 2*最小权值

我们需要尽可能的太高最小的权值，因此我们可以把最小的 k 个数设置成无限大，那么最终的答案在最小值*2和 \(\min(a_i,a_{i+1})\) 中取最小值。

对于两种情况，取最优（最大）解。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
int a[N], b[N];

void solve() {
    int ans[2] = {0, 0};
    priority_queue<PII, vector<PII>, greater<PII>> q;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        q.push({a[i], i});
    }

    for (int i = 0; i < m - 1; i++) {
        auto [x, id] = q.top();
        q.pop();
        a[id] = int(1e9);
        q.push({a[id], id});
    }

    for (int i = 1; i <= n; i++) b[i] = a[i];

    // case 1
    sort(a + 1, a + n + 1);
    ans[0] = min(a[1] * 2, a[n]);

    // case 2
    auto [x, id] = q.top();
    b[id] = int(1e9);
    int maxd = 0;
    for (int i = 1; i < n; i++)
        maxd = max(maxd, min(b[i], b[i + 1]));
    sort(b + 1, b + n + 1);
    ans[1] = min(b[1] * 2, maxd);
    cout << max(ans[0], ans[1]) << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
回到页面顶部