题意

有一个圆桌，总共有 $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$ 判断大小关系即可。

代码

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