Codeforces-Round-513-D-Social-Circles

博主博客

题目链接

题意：

有n个人，及每个人坐位置时左右需要有多少空椅子，求所有人入座至少需要多少椅子

题解：

利用贪心，将所有人的右边需要空的椅子数存在a数组里，右边需要空的椅子数存在b数组里，然后排序，将对应下标的max（a[i],b[i]）加起来再加上n，就是答案，因为大的和大的一合一起可以保证省去椅子最大

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
int a[maxn], b[maxn];
int main(int argc, char *argv[]) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d%d", &a[i], &b[i]);
	sort(a, a + n);
	sort(b, b + n);
	ll ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		ans += max(a[i], b[i]);
	}
	printf("%lld\n", ans+n);
	return 0;
}