题意简述

有 $n$ 个灯，第 $i$ 个灯在时刻 $a_i$ 安装并立即点亮，之后每隔 $k$ 分钟切换一次状态（开→关→开→…）。即对于整数 $t\ge 0$，灯在时间段 $[a_i+2tk,\; a_i+(2t+1)k-1]$ 内是亮的。求最早的时刻 $x$，使得所有灯都亮着，或判断无解。

数学转化

灯 $i$ 在时刻 $x$ 亮着，当且仅当 $(x - a_i) \bmod (2k) < k$。
设 $b_i = a_i \bmod (2k)$，则条件等价于 $x \bmod (2k)$ 落在区间 $I_i = [b_i,\; (b_i + k - 1) \bmod (2k)]$ 内（模 $2k$ 意义下的循环区间）。

同时 $x$ 必须不小于所有 $a_i$，即 $x \ge M = \max a_i$。

于是问题变为：找到一个整数 $r \in [0, 2k-1]$，使得 $r$ 被所有 $I_i$ 覆盖，并且满足 $x \ge M$ 且 $x \equiv r \pmod{2k}$ 的最小 $x$。

算法

1. 求出 $M = \max a_i$。
2. 使用差分数组 $\text{diff}[0..2k]$ 记录区间覆盖。对于每个 $a_i$：
   • $b = a_i \bmod (2k)$；
   • $L = b$，$R = (b + k - 1) \bmod (2k)$；
   • 若 $L \le R$，则 $\text{diff}[L] \mathrel{+}= 1$，$\text{diff}[R+1] \mathrel{-}= 1$；
   • 否则，$\text{diff}[L] \mathrel{+}= 1$，$\text{diff}[2k] \mathrel{-}= 1$；$\text{diff}[0] \mathrel{+}= 1$，$\text{diff}[R+1] \mathrel{-}= 1$。
3. 求前缀和得到每个余数 $r$ 的覆盖次数 $\text{cov}[r]$。
4. 遍历 $r$，若 $\text{cov}[r] = n$，则计算候选 $x$：
   • 令 $\textit{base} = M - (M \bmod (2k))$。
   • 若 $r \ge M \bmod (2k)$，则 $x = \textit{base} + r$；
   • 否则 $x = \textit{base} + 2k + r$。
   • 用所有候选 $x$ 的最小值更新答案。
5. 若没有任何 $r$ 满足 $\text{cov}[r]=n$，输出 $-1$；否则输出最小 $x$。

时间复杂度 $O(n + k)$，空间 $O(k)$。由于 $\sum n \le 2\times 10^5$ 且 $k\le n$，总复杂度在时限内轻松通过。

参考代码

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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    int mod = 2 * k;
    vector<int> diff(mod + 2, 0);  // 差分数组

    for (int x : a) {
        int b = x % mod;
        int L = b;
        int R = (b + k - 1) % mod;
        if (L <= R) {
            diff[L] += 1;
            diff[R + 1] -= 1;
        } else {
            diff[L] += 1;
            diff[mod] -= 1;       // 标记到 mod-1 为止，diff[mod] 用于前缀和
            diff[0] += 1;
            diff[R + 1] -= 1;
        }
    }

    vector<int> cov(mod);
    int cur = 0;
    for (int i = 0; i < mod; ++i) {
        cur += diff[i];
        cov[i] = cur;
    }

    ll ans = LLONG_MAX;
    int base = mx - (mx % mod);
    for (int r = 0; r < mod; ++r) {
        if (cov[r] == n) {
            ll x;
            if (r >= mx % mod) {
                x = base + r;
            } else {
                x = base + mod + r;
            }
            ans = min(ans, x);
        }
    }

    if (ans == LLONG_MAX) cout << "-1\n";
    else cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}