CF1993C Light Switches 题解

题目大意

有 \(n\) 盏灯，第 \(i\) 盏灯亮着的时间为 \([a_i+bk,a_i+(b+1)k-1]\)，其中 \(k\) 为给定常数，\(b\) 为任意非负偶数。求一个最小的 \(t\)，使得在时间 \(t\) 所有灯都是亮着的。

Solve

令 \(m=2k\)，显然所有灯的开关状态以 \(m\) 为周期，所以我们考虑把所有灯的开关状态映射到 \([0,m)\)，并求出每个灯映射的偏移量 \(d_i\)，即需要往前推多少个周期才能把开关状态映射到 \([0,m)\)，显然有 \(d_i=\lfloor{a_i\over m}\rfloor\)，那么映射后，这盏灯开着的区间即为 \([a_i\bmod m,a_i\bmod m+k-1]\)。

对于答案，取 \(\min\limits_{cnt_t=n}\{t+mx_t\times m\}\)，其中 \(t=0,1,\dots,m-1\)，\(cnt_t\) 为在 \(t\) 时刻为开着的灯的个数，\(mx_t\) 为在 \(t\) 时刻为开着的灯的偏移量的最大值。

但有一些细节。考虑有一些灯的开关状态在 \([0,m)\) 内可能是 11100011 这样的，\(1\) 在两边。这时候左边的 \(1\) 的偏移量为 \(\lfloor{a_i\over m}\rfloor+1\)，右侧的 \(1\) 的偏移量为 \(\lfloor{a_i\over m}\rfloor\)。

至于具体怎么维护 \(cnt_t\) 和 \(mx_t\)，显然可以上数据结构比如线段树，但这里提供一种不用数据结构的方法。

考虑借用扫描线的思想，对于每个 \(a_i\)，将对应区间左端点的 \(cnt\) 加上 \(1\)，右端点的 \(cnt\) 减去 \(1\)（相当于差分），遍历 \(t\) 时前缀和统计即可。而对于 \(mx\)，考虑在区间左端点插入二元组 \((d_i,1)\)，右端点插入二元组 \((d_i,0)\)。遍历 \(t\) 时，先操作 \(t\) 上的所有二元组，开一个 set，若二元组第二维是 \(1\)，则将 \(d_i\) 加入，否则删除。那么 \(mx_t\) 即为 set 的末尾元素。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	short f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=2e5+10;
int t,n,k,c[N<<1],ans,m;
struct zzn{int x;bool op;};
vector<zzn>q[N<<1];
multiset<int>s;//注意可能有相等的元素，故需要multiset
signed main()
{
	t=read();
	while(t--)
	{
		n=read();k=read();ans=1e18;m=k<<1;
		s.clear();
		for(int i=0;i<m;i=-~i)	c[i]=0,q[i].clear();
		for(int i=1,a;i<=n;i=-~i)
		{
			a=read();
			c[a%m]++,q[a%m].push_back({a/m,1});
			if(a%m+k<m)
				c[a%m+k]--,q[a%m+k].push_back({a/m,0});
			else//对应上文中 1 在左右两侧的情况
				c[0]++,q[0].push_back({a/m+1,1}),
				c[(a%m+k)%m]--,q[(a%m+k)%m].push_back({a/m+1,0});
		}
		for(int i=0,cnt=0;i<m;i=-~i)
		{
			cnt+=c[i];
			for(zzn j:q[i])
			{
				if(j.op)	s.insert(j.x);
				else	s.erase(s.find(j.x));//相等的元素只删除一个
			}
			if(cnt==n)	ans=min(ans,i+(*--s.end())*m);
		}
		if(ans==1e18)	puts("-1");
		else	printf("%lld\n",ans);
	}
	return 0;
}