记录编号	445875	评测结果	AAAAAAAWWW
题目名称	不平凡的boss	最终得分	70
用户昵称	Ostmbh	是否通过	未通过
代码语言	C++	运行时间	0.649 s
提交时间	2017-09-06 22:07:43	内存使用	5.66 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100000+10;
struct T{
	int x,y,z,id;
}A[maxn],B[maxn],C[maxn];
int n;
int vis[maxn];
int z[maxn];
inline bool cmp(T a,T b){
	return a.x<b.x;
}
inline bool cmp2(T a,T b){
	return a.y<b.y;
}
inline bool cmp3(T a,T b){
	return a.z<b.z;
}
inline void work1(){
	sort(A+1,A+n+1,cmp);
	long long maxb=0,maxc=0;
	long long ans=A[n].x;
	long long equal=0;
	for(int i=n;i>=1;i--){
		if(A[i].y>maxb&&A[i].z<=maxc)
			maxb=A[i].y;
		else if(A[i].y<=maxb&&A[i].z>maxc)
			maxc=A[i].z;
		else {
			if(A[i].y-maxb>A[i].z-maxc)
				maxc=A[i].z;
			else if(A[i].y-maxb<A[i].z-maxc)
				maxb=A[i].y;
			else equal+=A[i].y-maxb;
		}
		if(A[i-1].x+maxb+maxc-equal<ans)
			ans=A[i-1].x+maxb+maxc-equal;
	}
	printf("%lld\n",ans);
}
inline void work2(){
	sort(A+1,A+n+1,cmp);
	long long maxb=0;
	long long ans=A[n].x;
	for(int i=n;i>=1;i--){
		maxb=max(maxb,(long long)A[i].y);
		if(maxb+A[i-1].x<ans)
			ans=maxb+A[i-1].x;
	}
	printf("%lld\n",ans);
}
inline void work3(){
	sort(A+1,A+n+1,cmp);
	sort(B+1,B+n+1,cmp2);
	int ans=0x7fffffff;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++){
			for(int k=1;k<=n;k++)
				vis[k]=0;
			int left=n;
			for(int k=1;k<=i;k++){
				if(!vis[A[k].id]){
					vis[A[k].id]=1;
					left--;
				}
			}
			for(int k=1;k<=j;k++){
				if(!vis[B[k].id]){
					vis[B[k].id]=1;
					left--;
				}
			}
			int maxx=0;
			for(int k=1;k<=n;k++)
				if(!vis[k])
					maxx=max(z[k],maxx);
			if(maxx+A[i].x+B[j].y<ans)
				ans=maxx+A[i].x+B[j].y;
		}
	printf("%d\n",ans);
}
int main(){
	freopen("playwithboss.in","r",stdin);
	freopen("playwithboss.out","w",stdout);
	int opt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&A[i].x,&A[i].y,&A[i].z);
		B[i].x=A[i].x,B[i].y=A[i].y,B[i].z=A[i].z;
		A[i].id=i;
		B[i].id=i;
		z[i]=A[i].z;
		if(A[i].z!=100000000)
			opt=1;
	}
	if(!opt)
		work2();
	else if(n<=300)
		work3();
	else work1();
return 0;
}