現(xiàn)在有$N$個(gè)人,每一個(gè)人都不想周?chē)娜俗秒x他很近,所以在他的左邊要放$L_i$張椅子,右邊要放$R_i$張椅子.現(xiàn)在他們要坐成若干個(gè)圈,請(qǐng)問(wèn)最少要放多少?gòu)堃巫?注意:可以一個(gè)人坐在一個(gè)圈內(nèi).每一個(gè)人還需要坐一張椅子.

?

?

大力結(jié)論題……

手推了一下發(fā)現(xiàn)可以把$l_i$和$r_i$分別排個(gè)序，然后就是隨便連邊反正肯定會(huì)成環(huán)

然后設(shè)邊連著$l_i$和$r_j$，那么對(duì)答案貢獻(xiàn)就是$max(l_i,r_j)$

然后yy了一下發(fā)現(xiàn)sort之后對(duì)應(yīng)下標(biāo)的連邊即可

還有不要忘了所有人都有一把椅子

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\n",res); 27 return 0; 28 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/bztMinamoto/p/9765857.html

總結(jié)

以上是生活随笔為你收集整理的CF1060D Social Circles的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。