CF1704C Virus

题意

有一个长度为\(n\)的环，即对于\(1\leq i\leq n\)，满足第\(i\)个与第\(i+1\)个房子相邻，特别地，第 \(n\) 个房子与第 \(1\) 个房子也相邻。

一开始，这 \(n\) 个房子中有 \(m\) 个房子被病毒感染了。在之后的每天早上，都可以选择一个未被感染的房子并对其进行保护，被保护过的房子不会被病毒感染。随后，被染上病毒的房子都会传染他两边的房子，被保护的房子除外。

Cirno 想要阻止病毒的传播，若他采用最优策略去保护房子，请求出最终被感染房子数的最小值。

思路

我们可以将题目中的\(n\)个房子以被感染的房子为端点分成若干段。

很明显，如果我们想要尽量多的保护房子，那么就应该优先对长度较大的进行操作

那么，假设在决定保护这一段房子之前已经过了\(k\)天，那么这个段房子中就已经被感染了\(4k\)个，而如果想把这一段都保护起来，就需要将他的两段都封住。

那么在第\(k\)天决定保护这段房子，到第\(k+1\)天把他的端点都峰上，就一共需要牺牲\(4k+1\)个房子

需要注意，如果剩下的线段只剩\(1\)个房子了，那他就只需要保护一端（毕竟一端其实就相当于两端），需要特判一下

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=1e5+10;
int n,m,now,ans;
int a[Maxn],f[Maxn];
void run()
{
	cin>>n>>m;now=0;ans=0;a[0]=1;
	for(int i=1;i<=m;i++) cin>>a[i];
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++) f[i]=a[i]-a[i-1]-1;
	f[1]+=(n-a[m])+1;
	sort(f+1,f+m+1);
	for(int i=m;i>=1;i--)
	{
		if(f[i]-now==1) ans+=1; 
		else ans+=max((int)0,f[i]-now-1);
		now+=4;
	}
	cout<<n-ans<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run();
}