CF1060D Solution

题目链接

题解

因为由(n)个点、(n)条边组成的图一定为若干个环，所以不需考虑(l,r)在具体客人中的分配。易得两人间空隔的椅子数(=max(l_i,r_i))，而我们需要找到一种排序方式使得(max(l_i,r_i)+max(l_{i+1},r_{i+1})le max(l_i,r_{i+1})+max(l_{i+1},r_i))：将(l,r)从小到大排序（从大到小亦可），(ans=sumlimits_{i=1}^nmax(l_i,r_i))。证明略。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int l[N],r[N];
signed main()
{
	int n,ans=0;
	scanf("%lld",&n); 
	for(int i=1;i<=n;i++) scanf("%lld%lld",&l[i],&r[i]);
	sort(l+1,l+n+1); sort(r+1,r+n+1);
	for(int i=1;i<=n;i++) ans+=max(l[i],r[i]);
	printf("%lld",ans+n);
	return 0;
}