专栏文章

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

WWarren1022
P14458题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9xxv9
此快照首次捕获于
2025/12/01 22:58
3 个月前
此快照最后确认于
2025/12/01 22:58
3 个月前
查看原文

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

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

思路

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

提醒

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

Ac Code

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...