现在有$N$个人,每一个人都不想周围的人坐得离他很近,所以在他的左边要放$L_i$张椅子,右边要放$R_i$张椅子.
现在他们要坐成若干个圈,请问最少要放多少张椅子.
注意:可以一个人坐在一个圈内.每一个人还需要坐一张椅子.大力结论题……
手推了一下发现可以把$l_i$和$r_i$分别排个序，然后就是随便连边反正肯定会成环
然后设边连着$l_i$和$r_j$，那么对答案贡献就是$max(l_i,r_j)$
然后yy了一下发现sort之后对应下标的连边即可
还有不要忘了所有人都有一把椅子
1 //minamoto 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8 #define num ch-'0' 9 char ch;bool flag=0;int res; 10 while(!isdigit(ch=getc())) 11 (ch=='-')&&(flag=true); 12 for(res=num;isdigit(ch=getc());res=res*10+num); 13 (flag)&&(res=-res); 14 #undef num 15 return res; 16 } 17 const int N=1e5+5; 18 int a[N],b[N],n;ll res=0; 19 int main(){ 20 // freopen("testdata.in","r",stdin); 21 res=n=read(); 22 for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(); 23 sort(a+1,a+1+n),sort(b+1,b+1+n); 24 for(int i=1;i<=n;++i) 25 res+=a[i]>b[i]?a[i]:b[i]; 26 printf("%lld ",res); 27 return 0; 28 }