题解 CF1668B【Social Distance】

## 题意 有一个**圆桌**，总共有 $m$ 个座位。现在有 $n$ 个人要围着圆桌坐下，但他们每个人都希望自己**左右两边都**至少有 $a[i]$ 个座位是空的。问，是否存在一种座位分配方案，可以同时满足 $n$ 个人的要求？ ## 思路 假设现在有一群人，其中有甲乙丙，这三人的要求分别是 $100$，$50$，$1$。可以看出：甲是最难安排的，因为他的要求最苛刻；而丙很好打发，他只需要自己身边有总共两个空位就满足了。所以要尽量让甲乙相邻，而不是甲丙挨着坐。这样才能尽量降低空间的浪费。 于是不难想到一种贪心的思路：对 $a$ 数组排序。让要求相近的人挨着坐。设 $\texttt{dis(x, y)}$ 表示第 $x$ 人和第 $y$ 人之间的间距，那么： - $\texttt{dis(1, 2)}$ = $a[2]$ - $\texttt{dis(2, 3)}$ = $a[3]$ - $\texttt{dis(3, 4)}$ = $a[4]$ - ... - $\texttt{dis(n - 1, n)}$ = $a[n]$ - $\texttt{dis(n, 1)}$ = $a[n]$ 于是所需要的**空座位**总数量，就是上述这一坨求和。再加上 $n$ 个人所占用的座位，与 $m$ 判断大小关系即可。 ## 代码 ```cpp void solution() { int n, m; read(n, m); m -= n; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++i) read(a[i]); if (m < 0) return void(std::cout << "NO\n"); ll sum = std::accumulate(a.begin() + 1, a.end(), 0ll); sum -= *std::min_element(a.begin() + 1, a.end()); sum += *std::max_element(a.begin() + 1, a.end()); if (m >= sum) return void(std::cout << "YES\n"); std::cout << "NO\n"; } ```