题目链接:https://www.luogu.com.cn/problem/P1094
这里会分三种思路来解决:
- 方法一:贪心+枚举答案 \(O(n^2)\)
- 方法二:贪心+二分答案 \(O(n \log n)\)
- 方法三:贪心 \(O(n)\)
方法一:贪心+枚举答案 \(O(n^2)\)
我可以开一个 check(m)
函数去判断能够抽成 \(m\) 对,如果能抽成 \(m\) 对则对应的答案是 \(n-m\)。然后从小到大枚举 \(m\) ,找到最大的 check(m)
为 \(true\) 的 \(m\) 即为我要求的答案。
示例代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30030;
int n, w, a[maxn], ans;
bool check(int m) {
for (int i = 1; i <= m; i ++) if (a[i] + a[2*m+1-i] > w) return false;
return true;
}
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a+1, a+1+n);
ans = n;
for (int i = 1; i <= n/2; i ++) {
if (!check(i)) break;
ans = n - i;
}
cout << ans << endl;
return 0;
}
方法二:贪心+二分答案 \(O(n \log n)\)
和上面的思想是一样的,只不过答案可以二分,所以就是进行了将 “枚举答案” 到 “二分答案” 的一个转换。
示例代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30030;
int n, w, a[maxn], ans;
bool check(int m) {
for (int i = 1; i <= m; i ++) if (a[i] + a[2*m+1-i] > w) return false;
return true;
}
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a+1, a+1+n);
ans = n;
int L = 1, R = n/2;
while (L <= R) {
int mid = (L + R) / 2;
if (check(mid)) ans = n - mid, L = mid + 1;
else R = mid - 1;
}
cout << ans << endl;
return 0;
}
方法三:贪心 \(O(n)\)
基于的贪心思想是如果最多能凑成 \(m\) 对,则 \(m\) 对中较小的那 \(m\) 个数可以为最小的 \(m\) 个数,在这种情况下优先选大的了最小的、次小的…… 配对。
示例代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30030;
int n, w, a[maxn], c;
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a+1, a+1+n);
int i = 1, j = n;
while (i < j) {
if (a[i] + a[j] <= w) i ++, j --, c ++;
else j --;
}
cout << n - c << endl;
return 0;
}