https://codeforces.com/contest/1993/problem/C
题目大意
给定 $n$ 盏灯和 $n$ 长数组 $a_i (1 \le a_i \le 10^9)$ 和 $k$，$1 \le k \le n \le 2 \cdot 10^5$。
起初 $n$ 盏灯都不亮。$i$ 位置的灯在 $a_i$ 时刻第一次点亮，之后每过 $k$ 单位时间点亮熄灭状态反转一次。问最早什么时刻，所有灯都亮。
简要题解
显然时间过去非常久之后，灯的状态变化会是一个 $2k$ 长的循环。每盏灯在 $a_i % 2k ~ (a_i % 2k + k - 1) % 2k$ 的时段被点亮。
这个循环从 $a_i$ 最大的灯第一次点亮开始，因此检查 $a_i$ 及向后的所有时刻是否所有灯都亮就行了（显然答案也不可能早于最晚第一次点亮的灯的点亮时间）。问题变成了一个环上的区间和问题。$t$ 时刻所有灯都亮，即为 $t - k + 1 ~ t$ 区段内所有的灯都亮。如果检查了 $2k$ 个时刻都不行，则无解。
复杂度
$T$：$O(n + k)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<int> cnt(k * 2);
int mx = 0;
for (int i : a) {
cmax(mx, i);
cnt[i % (k * 2)]++;
}
for (int i = 1; i < (k * 2); i++) {
cnt[i] += cnt[i - 1];
}
auto sum = [&](int p) {
p %= (k * 2);
if (p >= k) {
return cnt[p] - cnt[p - k];
}
int ans = cnt[p];
int left = k - (p + 1);
if (left) ans += cnt[k * 2 - 1] - cnt[k * 2 - 1 - left];
return ans;
};
for (int i = mx, j = 0; j < (k * 2); i++, j++) {
if (sum(i) == n) {
cout << i << '\n';
return;
}
}
cout << "-1\n";
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [数学] 判断数字能否被 x 整除