计蒜客-A2227 轻重搭配 题解

题目大意

总共有n个人去参观，每个人需要一张门票，但是体重为x的人可以和体重大于等于2x的人共用一张门票，求最小的门票数量。

解题思路

为啥我的贪心就是不会啊。。。

哭了。

本来的我想的思路是，如果能匹配，那就选尽量小的，也就是恰好的。

但是这个思路不好写，而且应该会T。

正解应该是按体重从小到大排序后用双指针，一个从$\Large \frac {n}{2}$开始，一个从$n$开始。

因为他们最多匹配$\Large \frac {n}{2}$对，所以只需要从$\Large \frac {n}{2}$开始。

满足条件就双指针向前移动，否则只有第一个指针移动。

完整代码

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

const int N = 5e5 + 5;
int flag[N],cnt[N],num[N];

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}
	sort(num + 1, num + 1 + n);
	int ans = n;
	int l = n / 2, r = n;
	while (l) {
		if (num[l] * 2 > num[r])	l--;
		else ans--, l--, r--;
	}
	cout << ans << endl;
}