题解：CF2153C Symmetrical Polygons

来不及写就被我妈要求回去睡觉了。

考虑对称图形的性质：

有 $\ge 3$ 条边。
边两两配对，只剩下 $0/1/2$ 条边。

只剩下

0

条边是好处理的，但是要注意必须至少有两对相等边。

剩下

1

条边需要使其小于其他边的总和。

剩下

2

条边要求较长边小于其他边的总和（包括另外一条剩余边）。

用 map 实现的，时间复杂度

O(n\log n)

。

CPP

#include<bits/stdc++.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline ll read(){
	ll a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(ll x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(ll x){
	write(x),putchar(' ');
} 
inline void write2(ll x){
	write(x),putchar('\n');
}
ll n;
ll a[5*114514]; 
ll b[5*114514];
map<ll,ll> c;
void solve(){
	ll tag=0;
	n=read();
	ll include13=0;
	for(ll i=1;i<=n;i++){
		a[i]=read();
		c[a[i]]++;
		if(c[a[i]]==2){
			include13+=a[i]*2;
			tag++;
			c[a[i]]=0;	//解除效应！  
		}
	}
	ll idx=0;
	for(ll i=1;i<=n;i++){
		if(c[a[i]]){
			b[++idx]=a[i];
			c[a[i]]=0;
		}
	} 
	sort(b+1,b+idx+1);
	ll include13_fAKe=include13;	//include13_fAKe 才是真正的最后答案  
	if(tag<=1)	include13_fAKe=0;
	for(ll i=1;i<=idx;i++){
		if(b[i]<include13){
			include13_fAKe=max(include13+b[i],include13_fAKe);
		} 
		if(i!=idx){
			if(b[i+1]-b[i]<include13){
				include13_fAKe=max(include13+b[i+1]+b[i],include13_fAKe);
			}
		}
	}
	write2(include13_fAKe);
} 
int main(){
	ll T=read();
	while(T--)	solve();
	putchar('\n');
	return 0;
} //还是不习惯你不在 这身份转变太快

题解：CF2153C Symmetrical Polygons

文章操作

相关推荐

评论

题解：CF2153C Symmetrical Polygons