题解：P14458 [ICPC 2025 Xi'an R] Let' s Make a Convex!

Warren1022 · 2025-11-11 21:39:10 · 题解

P14458 [ICPC 2025 Xi'an R] Let' s Make a Convex!题解

真的没有dalao觉得这题和今年CSP-J的T4似曾相识么？

思路

• 把木棍长度按升序排列。
• 前缀和数组储存与它前面的木棍长度的和。
• 二分查找寻找可选的木棍。

  提醒

  凸多边形图有一个定义：对于凸多边形图的所有边，有所有边之和 > 最长边。

  Ac Code

  #include <bits/stdc++.h>
  using namespace std;
  const int N = 2e5 + 10;
  long long _, n, a[N], s[N], ans[N], la;
  int main() {
  cin >> _;
  while (_--) {
      scanf("%lld", &n);
      la = n;
      for (int i = 1; i <= n; i++)
          scanf("%lld", &a[i]);
      sort(a + 1, a + n + 1);
      for (int i = 1; i <= n; i++)
          s[i] = s[i - 1] + a[i];
      for (int i = n; i > 2; i--) {
          if (s[i - 1] <= a[i])
              continue;
          int l = 0, r = i - 3;
          while (l < r) {
              int mid = l + r + 1 >> 1;
              if (s[i - 1] - s[mid] > a[i])
                  l = mid;
              else
                  r = mid - 1;
          }
          for (int j = max(1LL, i - la + 1); j <= l + 1; j++)
              ans[i - j + 1] = s[i] - s[j - 1];
          if (max(1LL, i - la + 1) <= l + 1)
              la = i - l - 1;
      }
      for (int i = 1; i <= n; i++)
          printf("%lld ", ans[i]), ans[i] = 0;
      printf("\n");
  }
  return 0;
  }