C. Light Switches - Codeforces Round 963 (Div. 2)

Lastmod: 2024-08-05 周一 23:28:20

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;
}

Prev: D. Med-imize - Codeforces Round 963 (Div. 2)
Next: [数学] 判断数字能否被 x 整除

Gitalking ...

	#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;
	}