计蒜客-A2227 轻重搭配 题解

题目大意

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

解题思路

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

哭了。

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

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

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

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

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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信