C. Virus（贪心）

题目

题意

有n只牛，它们围成一个环。其中第1只牛和第n只牛相邻。
初始有若干只(m)感染的牛。
对于每一秒，会发生以下事情。

• 选择未感染的一只牛，将它保护起来，使得他终生不感染。
• 对于没有被保护的、未感染的牛，如果它至少有一只相邻的牛被感染，那么它也被感染。

对于每一秒，应保护哪些牛，使得最终被感染的牛，数量最少。输出最终被感染的牛的数量。

数据范围
$1<=n<=10^9,1<=m<=10^5,n$

思路

贪心，计算最终可以保护的牛的数量。
我们把所有初始时，所有的非感染牛区间，都提取出来，并按照从大到小顺序排列。
并按大区间优先处理的原则，尽量去阻止感染牛的蔓延。

详见代码

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;

int n, m;
int a[maxn], b[maxn];
int cal() {
    
	int res = 0;// 最多可以保护的牛的数量 
	for (int i = 0; i < m; ++i) {
    
		b[i] = a[i+1] - a[i] - 1;
	}
	sort(b, b + m);// 排序 
	int cur = 0;// 时间戳 
	for (int i = m - 1; i >= 0; --i) {
    
		if (b[i] <= 2 * cur) break;// 如果所有牛都被感染了，停止处理 
		if (b[i] == 2 * cur + 1) {
    // 只有一只牛没感染 
			res += 1;
			++cur;
		} else {
    // 可以放两只牛的场景 
			res += b[i] - (2 * cur + 1);
			cur += 2;
		}
	}
	return n - res;
}
void solve() {
    
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
    
		scanf("%d", &a[i]);
	}
	sort(a, a + m);
	a[m] = a[0] + n;// 添加个a[m]，方便处理a[m-1]和a[0] 

	int res = cal();
	printf("%d\n", res);
}
int main() {
    
	int t;
	scanf("%d", &t);
	while (t--) {
    
		solve();
	}
}

/* 20 3 3 7 12 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 */

最后

weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~