D. Empty Graph（贪心/二分）

题目
参考

题意

给定n个点，每个点权值为a[i]，定义u到v的无向边的边权为min(a[u],a[u+1],…,a[v])(u 可以选择k个点，并把它的权值改为1到1000000000的任意整数。
问通过k次修改后，能使该无向图的直径最大。

定义图的直径为max(dis[u][v]) 1<=u < v<=n，dis[u][v]表示u到v的最短路径。

思路

1. 对于k次操作，我们可以贪心地把改的点，点权改为最大，即1000000000
2. 对于任意点u 证明：假设a[pos] = min(a[1],…,a[n])。如果u<=pos<=v，则dis[u][v]=a[pos]，满足要求；如果posv，则
   $dis[u][v]=min(min(a[u],...,a[v]),dis[u][pos]+dis[pos][v])=min(min(a[u],...,a[v]),2\ast min(a[1],...,a[n]))$
3. 图的直径取值为$max(dis[i][i+1])=min(max(dis[i][i+1]),2\ast min(a[1],...,a[n])),(1<=i<n)$
   证明：因为两点的距离是随节点数的增多而降低的，因此，要求图的直径，我们只需关注相邻节点的距离即可。

二分

利用上述结论3。对于判断是否可以达到答案值res

• 我们需要把=res
• 如果剩余修改次数不够，则为false
• 如果剩余修改次数大于1，我们可以选择把两个相邻点都置为1000000000，此时max(dis[i][i+1])=1000000000>=res，为true
• 如果剩余修改次数为1，我们则把权值最大的节点的邻居节点修改为1000000000，此时max(dis[i][i+1])=max(a[1],…,a[n])，我们只需判断max(a[1],…,a[n])是否大于res
• 如果剩余修改次数为0，我们需要计算下当前的图的直径，并与res比较。

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int n, k;
ll a[maxn];
vector<pair<int, ll> > poses;
void pop_back() {
	for (auto p: poses) {
		a[p.first] = p.second;
	}
}
bool check(ll val) {
	poses.clear();
	int count = 0;
	ll mx = 1, mn = 1000000000;
	for (int i = 1; i <= n; ++i) {
		if (a[i] * 2 < val) {
			poses.push_back({i, a[i]});
			a[i] = 1000000000;
			++count;
		}
		mn = min(mn, a[i]);
		mx = max(mx, a[i]);
	}
	
	count = k - count;
	if (count < 0) {
		pop_back();
		return false;
	} else if (count > 1) {
		pop_back();
		return true;
	} else if (count == 1) {
		pop_back();
		return mx >= val;
	}
	
	// count == 0
	ll res = min(a[1], a[2]);
	for (int i = 2; i + 1 <= n; ++i) {
		res = max(res, min(a[i], a[i+1]));
	}

	res = min(res, 2 * mn);
	
	pop_back();
	return res >= val;
}
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	ll l = 1, r = 1000000000, mid;
	while (l < r) {
		mid = (l + r + 1) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	printf("%d\n", l);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

贪心

利用结论3，我们可以将k-1次操作应用到权值最小的前k-1个节点上，再把剩余的一次操作，替换到每个节点，计算每个情况的直径，取所有情况的最大值。
证明：
当k为1时，用上述策略，显然成立。
当k大于1时，因为答案为min(max(dis[i][i+1]), 2min(a[1],…,a[n]))，我们尽力去最大化max(dis[i][i+1])和2min(a[1],…,a[n])。对于max(dis[i][i+1])，我们只需要花费最多两次操作，即可让他变成1000000000（修改相邻的两个节点）；因此，剩余的次数，我们可以用来最大化min(a[1],…,a[n])。

替换k-1个节点后，要遍历替换每个节点的情况，我们可以用前缀、后缀思想做优化，详见代码。

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int n, k;
struct node {
	ll val;
	int pos;
}a[maxn];
bool cmp1(const node &a, const node &b) {
	return a.val < b.val;
}
bool cmp2(const node &a, const node &b) {
	return a.pos < b.pos;
}
ll mn_pre[maxn], mn_suf[maxn];
ll pre[maxn], suf[maxn];

void debug() {
	printf("a:\n");
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", a[i].val);
	}
	printf("\n-------------------------\n");
	
	printf("mn_pre:\n");
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", mn_pre[i]);
	}
	printf("\n-------------------------\n");
	
	printf("mn_suf:\n");
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", mn_suf[i]);
	}
	printf("\n-------------------------\n");
	
	printf("pre:\n");
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", pre[i]);
	}
	printf("\n-------------------------\n");
	
	printf("suf:\n");
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", suf[i]);
	}
	printf("\n-------------------------\n");
	
	
}
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i].val);
		a[i].pos = i;
	}
	sort(a + 1, a + n + 1, cmp1);
	for (int i = 1; i < k; ++i) {
		a[i].val = 1000000000;
	}
	sort(a + 1, a + n + 1, cmp2);
	
	
	
	mn_pre[1] = a[1].val;
	for (int i = 2; i <= n; ++i) {
		mn_pre[i] = min(mn_pre[i-1], a[i].val);
	}
	mn_suf[n] = a[n].val;
	for (int i = n - 1; i >= 1; --i) {
		mn_suf[i] = min(mn_suf[i+1], a[i].val);
	}
	pre[1] = 0;
	pre[2] = min(a[1].val, a[2].val);
	for (int i = 3; i <= n; ++i) {
		pre[i] = max(min(a[i].val, a[i-1].val), pre[i-1]);
	}
	suf[n] = 0;
	suf[n-1] = min(a[n-1].val, a[n].val);
	for (int i = n - 2; i >= 1; --i) {
		suf[i] = max(min(a[i].val, a[i+1].val), suf[i+1]);
	}
	
//	debug();
	
	ll res = 0;
	for (int i = 1; i <= n; ++i) {
		ll last = a[i].val;
		a[i].val = 1000000000;
		ll tmp = 0;// max(a[i], a[i+1])
		if (i > 1) {
			tmp = max(tmp, min(a[i-1].val, a[i].val));
		}
		if (i < n) {
			tmp = max(tmp, min(a[i].val, a[i+1].val));
		}
		if (i > 2) {
			tmp = max(tmp, pre[i-1]);
		}
		if (i < n - 1) {
			tmp = max(tmp, suf[i+1]);
		}
		
		ll mn = a[i].val;// min(a[1]...a[n])
		if (i > 1) {
			mn = min(mn, mn_pre[i-1]);
		}
		if (i < n) {
			mn = min(mn, mn_suf[i+1]);
		}
//		printf("%d: {%lld, %lld}\n", i, tmp, mn);
		res = max(res, min(tmp, 2 * mn));
		a[i].val = last;
	}
	printf("%lld\n", res);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

最后

如果觉得文章不错的话，weixin gongzhonghao 搜索下 对方正在debug，一起快乐刷题吧~