526互联

Codeforces Round 783 (Div. 2) B. Social Distance

发布时间 2023-09-13 15:37:02作者: zsxuan

\(m\) 张椅子被顺序排成一个圈，编号从 \(0\) 到 \(n - 1\) ， \(n\) 个人打算入座，第 \(i\) 个人希望左右 \(a_i\) 张椅子没有人坐。是否存在满足所有的意愿的情况下可以全部入座。\(n\) 个人不必顺序入座。

观察一：总共有 \(m\) 张椅子，\(n\) 个人至少需要 \(n\) 个座位。设排列 \(p\) 为入座顺序，余下 \(n - m\) 位置需满足 \(n - m \geq \sum_{i=1}^{n} max(p_i, p_{i \% m + 1})\) 。

观察二：若排列 \(p\) 为入座顺序，不同 \(p\) 的 \(\sum_{i=1}^{n} max(p_i, p_{i \% (n+1) + 1})\) 不同。

  1. 考虑 \(m\) 个结点组成一条链
    • 对于任意边上两个节点 \(p_i, p_j,\ a_{p_i} \geq a_{p_j}\) ，边权是 \(a_{p_i}\) 。
    • 对于任意两条邻边上三个节点 \(p_i, p_j, p_k,\ a_{p_i} \geq a_{p_j} \geq a_{p_k}\)
      • 若 \(p_i\) 不在中间，则边权和为 \(w_1 = a_{p_i} + a_{p_j}\) 。
      • 若 \(p_i\) 在中间，则边权和为 \(w_2 = a_{p_i} + a_{p_i}\) 。
      • 显然对于任意两条邻边，边上节点单调使边权和最小。于是整体的边上节点单调使 \(\sum_{i=1}^{n} max(a_i, a_{i\%(n+1)+1})\) 最小。
  2. 当 \(m\) 个节点组成一个环如何扩展？
    • 一定存在两条邻边，边权和为 \(w = p_i + p_i\) ，当 \(a_{p_i} = max_{j=1}^{n} a_{p_j}\) 。
    • 将排序好的链首位凭借，有且仅有两条邻边满足 \(w = p_n + p_n\) 。
    • 于是 \(m\) 个节点排序后，扩展为环依然满足 \(\sum_{i=1}^{n} max(a_i,a_i\%(n+1)+1)\) 最小 。

可以使用 \(O(n \log n)\) 做法直接排序，\(p_i\) 为第 \(i\) 位上原来的位置，然后判断 \(n + \sum_{i=2}^{n} a_{p_i} + a_{p_n} \leq m\) 。

实际上，假设已经排序，则 \(\sum_{i=2}^{n} a_{p_i} + a_{p_n}\) 与未排序的 \(\sum_{i=1}^{n} a_i - min_{i=1}^{n} a_i + max_{i=1}^{n} a_i\) 等价，于是可以 \(O(n)\) 预处理，然后 \(O(1)\) 求出。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
	int n, m; std::cin >> n >> m;
	std::vector<int> a(n);
	ll sum = 0; for (int i = 1; i <= n; i++) {
		std::cin >> a[i-1]; sum += a[i-1];
	}
	std::cout << (n + sum - *std::min_element(a.begin(), a.end()) + *std::max_element(a.begin(),a.end()) <= m ? "YES" : "NO") << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}