C. Virus (greedy)

题目

题意

有n只牛,它们围成一个环.其中第1Cow and CapnThe cow is next to each other.
There were a few at first(m)infected cattle.
对于每一秒,会发生以下事情.

• Select an uninfected cow,将它保护起来,Make him uninfected for life.
• for the unprotected、Uninfected cattle,If it has at least one adjacent cow that is infected,Then it is also infected.

对于每一秒,Which cattle should be protected,Makes eventually infected cattle,数量最少.Output the number of cattle that were eventually infected.

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

思路

贪心,Calculate the number of cattle that can ultimately be protected.
We put all initial time,All non-infected cattle intervals,都提取出来,并按照从大到小顺序排列.
并按Large areas are given priority的原则,Try to stop the spread of infected cattle.

详见代码

代码

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

int n, m;
int a[maxn], b[maxn];
int cal() {
    
	int res = 0;// The maximum number of cattle that can be protected 
	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 all cows are infected,停止处理 
		if (b[i] == 2 * cur + 1) {
    // Only one cow was not infected 
			res += 1;
			++cur;
		} else {
    // A scene where two cows can be placed 
			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,关注下,一起快乐刷题吧~