CF-1060D Social Circles 题解

题目大意

有n个客人，他们围绕着1个或者多个圈而坐。每一个人都需要左边空li个人，右边ri个人（空位可以重叠）。请问最少需要多少个座位。

解题思路

（想了好久没想到思路，后来发现是理解错了。。

其实就是蠢了。想着左边连左边了。

看了题解，发现就是贪心。。

每个人就是左边连着另外一个人的右边，那么我只要让他们的差值最小即可，这样浪费的座位数越小，也就是按照大小排序之后，取左边和右边中的最大值+1，便是两人之间一条边的最小贡献。（如果选出的恰好是同一个人的时候，就是一个人单独一个圈，也是相同的方法）

（zbw大佬说的对，贪心确实要多做题。。

第一次做到这种贪心。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
int l[N], r[N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)	cin >> l[i] >> r[i];
	sort(l + 1, l + 1 + n);
	sort(r + 1, r + 1 + n);
	long long ans = 0;//注意数据范围
	for (int i = 1; i <= n; i++)
		ans += max(l[i], r[i]) + 1;
	cout << ans << endl;
}