# C. Virus (greedy)

2022-08-06 09:23:51Luo gkv

## 题意

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.

1 < = n < = 1 0 9 , 1 < = m < = 1 0 5 , n 1<=n<=10^9,1<=m<=10^5,n

## 思路

We put all initial time,All non-infected cattle intervals,都提取出来,并按照从大到小顺序排列.

## 代码

#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 + n;// 添加个a[m],方便处理a[m-1]和a

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,关注下,一起快乐刷题吧~