题解：P12804 [AMPPZ 2019] Polygon

简化

仔细想想可以发现：一个凹多边形可以把凹进去的两条边不改变长度的情况下翻转出来，重复此操作可以让凹多边形变成凸的。

所以题目可以简化成求构造出的多边形可能的最大周长。

再简化

怎么判断一些线段是否可以连成多边形呢？

有一个性质：多边形的任意一个边一定小于于其他边的和。

在把问题化成：给定一个序列，求出里面和最大的子序列，子序列的任意一个值小于子序列的其他值的和。

证明

反证法。

假设有一个多边形，有一条边的长度大于其他边的和。这条边的两个端点是

x

和

y

。

x

到

y

有两条路径，一条是这条“特殊边”，另一条是其他边。这条边是直的。另一条路径上有其他端点，所以不是直的。

两点之间直线最短，所以这条边的长度小于其他边的和。与原假设矛盾。

实现

把这些边从小到大排序。可以发现答案是原来序列的前缀。

证明

因为从小到大排序了。从前往后选择的时候，如果一个值大于前面所有值的和了。那么也不能选择后面的值了，因为后面的值比这个值还要大。

由于要最大的周长，排序之后从后往前遍历，也就是从最大的前缀开始枚举。如果这个前缀满足最小值小于其他值的和，那么它可以围成多边形，那么输出这个前缀的和。

因为一个前缀的最小值是最后一个值，其他值就是长度比它小一的前缀。所以其他值的和就是前缀和。可以预处理出前缀和来优化。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long a[100010];
long long sum[100010];
void f(){
	long long n;
	cin>>n;
	for(long long i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	sum[0]=a[0];
	for(long long i=1;i<n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	for(long long i=n-1;i>=2;i--){
		if(a[i]<sum[i-1]){
			cout<<sum[i]<<endl;
			return;
		}
	}
	cout<<"0\n";
}
int main(){
	long long T;
	cin>>T;
	while(T--){
		f();
	}
}

题解：P12804 [AMPPZ 2019] Polygon

文章操作

简化

再简化

证明

实现

证明

代码

相关推荐

评论

题解：P12804 [AMPPZ 2019] Polygon