CF1993C Light Switches

题意简述

有一个包含 $n$ 个房间的公寓，每个房间的灯最初都是关着的。

公寓的主人决定在每个房间安装一个芯片，每个房间安装芯片的时间不同。具体来说，时间用数组 $a_1, a_2, \ldots, a_n$ 表示，其中 $a_i$ 是在第 $i$ 个房间安装芯片的时间（分钟）。

一旦芯片安装完成，它每隔 $k$ 分钟改变一次房间的灯状态——亮灯 $k$ 分钟，然后熄灯 $k$ 分钟，再亮灯 $k$ 分钟，以此类推。也就是说，第 $i$ 个房间的灯状态会在时间点 $a_i$，$a_i + k$，$a_i + 2k$，$a_i + 3k$，…… 发生改变。

求使所有房间的灯都亮着的最早时刻。

思路分析

我们注意到每盏灯的亮暗切换周期都是 $2k$，即 $t+2k$ 时的亮暗情况与 $t$ 时刻的亮暗情况相同。

既然灯的亮暗存在周期性变化，所以我们可以把 $n$ 盏灯的亮暗周期同步到一个相近的区间内。

这一部分可以通过 $a_i \gets (a_i \bmod 2k)$ 来实现。

这一操作同时也获得了 $[0,2k)$ 内每个时刻有多少盏灯恰好切换至亮灯状态。

令 $b_t$ 表示 $t$ 时刻有多少盏灯切换至亮灯状态。

可知 $bt = \sum\limits{i=0}^{2k-1} [t=(a_i \bmod 2k)]$。

接下来考虑如何统计。

因为每盏灯亮暗切换间隔为 $k$ 秒，所以我们可以统计一个长度为 $k$ 的时间区间内所有灯的亮暗情况。

如果一盏灯在左端点的时刻亮了，那么它正好会在右端点的时刻后一个时刻灭掉。

如果一盏灯被点亮的时间落在这个长度为 $k$ 的区间内，那么在右端点时，这盏灯一定还是亮着的。

如果这个区间内并不是所有的灯都亮着，我们就让这个区间向右移动一位。

如果在这个区间内，所有灯都亮着，那么这个区间的右端点即为一个答案。

因为上一次的移动添加了新的右端点后才使得所有灯都亮着，所以当前区间的右端点即为所求的最小的等待时间。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxN = 6e5 + 10;
int A[maxN];
int num[maxN];

inline void solve(){
    int N,K;
    scanf("%d%d",&N,&K);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
    for(int i = 0;i<=(K<<1);i++) num[i] = 0;

    int ma = -1;

    for(int i = 1;i<=N;i++){
        num[A[i] % (K << 1)]++;
        ma = max(ma,A[i]);
    }

    int cnt = 0;
    int ans = INT_MAX;

    for(int i = 0;i<= (K - 2);i++) cnt += num[i];

    int l = 0;
    int r = K - 1;

    while(l < (K << 1)){
        if(r >= (K << 1)) r -= (K << 1);

        cnt += num[r];

        if(cnt == N){
            int wait = (r - ma) % (K << 1);
            if(wait < 0) wait += (K << 1);
            ans = min(ans,ma+wait);
        }

        cnt -= num[l];

        l++,r++;
    }
    
    if(ans == INT_MAX) ans = -1;

    printf("%d\n",ans);

}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}