题干：
n 个同学去动物园参观，原本每人都需要买一张门票，但售票处推出了一个优惠活动，一个体重为 xx 的人可以和体重至少为 2x2x 配对，这样两人只需买一张票。现在给出了 nn 个人的体重，请你计算他们最少需要买几张门票？
输入格式
第一行一个整数 nn，表示人数。
第二行 nn 个整数，每个整数 a_iai 表示每个人的体重。
输出格式
一个整数，表示最少需要购买的门票数目。
数据范围
对于 30\%30% 的数据：1 \le n \le 251≤n≤25，1\le a_i \le 1001≤ai≤100。
对于 60\%60% 的数据：1 \le n \le 100001≤n≤10000，1\le a_i \le 10001≤ai≤1000。
对于 100\%100% 的数据：1 \le n \le 5\cdot 10^51≤n≤5⋅105，1\le a_i \le 10^51≤ai≤105。
样例解释
11 和 99 配对，77 和 33 配对，剩下 5,55,5 单独，一共买四张票。
样例输入复制
6
1 9 7 3 5 5 样例输出复制
4 解题报告：
这题贪心证明（同优则立法），一定可以从前n/2个数中选择就行了，然后从后面剩下的数（可能n/2 也可以 n/2 +1）中选择配对的。。
错误代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
set<int> ss;
set<int> :: iterator it,itt;
int main()
{
int n;
cin>>n;
for(int tmp,i = 1; i<=n; i++) {
scanf("%d",&tmp);ss.insert(tmp);
}
int ans = 0;
while(ss.size()) {
it = ss.begin();
itt = ss.lower_bound(*it * 2);
if(itt == ss.end()) break;
else ss.erase(itt),ss.erase(it),ans++;
}
cout << ss.size() + ans << endl;
return 0 ;
}
/*
6
1 3 5 5 7 9
*/ 一改：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX];
set<int> ss;
set<int> :: iterator it;
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d",a+i);
}
sort(a+1,a+n+1);
for(int i = n/2+1; i<=n; i++) {
ss.insert(a[i]);
}
int cur = 1;
while(ss.size() && cur <= n/2) {
it = ss.lower_bound(a[cur] * 2);
// printf("it = %d\n",*it);
if(it == ss.end()) break;
else ss.erase(it);
cur++;
}
cur--;
cout << /*ss.size() + n/2 - cur*/n-cur << endl;
return 0 ;
}
/*
6
1 3 5 5 7 9
*/ AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 6e5 + 5;
int a[MAX];
multiset<int> ss;
multiset<int> :: iterator it;
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d",a+i);
}
sort(a+1,a+n+1);
for(int i = n/2+1; i<=n; i++) {
ss.insert(a[i]);
}
int ans = 0;
int cur = 1;
while(ss.size() && cur <= n/2) {
it = ss.lower_bound(a[cur] * 2);
// printf("it = %d\n",*it);
if(it == ss.end()) break;
else ss.erase(it),ans++;
cur++;
}
cur--;
cout << ans + (n/2 - cur) + ss.size() << endl;
return 0 ;
}
/*
6
1 3 5 5 7 9
*/ 注意点：最后答案的计算，来自三部分别忘了（其实根据标程那个想法更好想）。
cur从1开始而非从0开始。
用multiset，而不是set。
还有一个坑点，，数据范围是5e5，，我一般习惯2e5了，，所以一直WA。。
或者最后答案这么计算：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 6e5 + 5;
int a[MAX];
multiset<int> ss;
multiset<int> :: iterator it;
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d",a+i);
}
sort(a+1,a+n+1);
for(int i = n/2+1; i<=n; i++) {
ss.insert(a[i]);
}
int cur = 1;
while(ss.size() && cur <= n/2) {
it = ss.lower_bound(a[cur] * 2);
// printf("it = %d\n",*it);
if(it == ss.end()) break;
else ss.erase(it);
cur++;
}
cur--;
cout << /*ss.size() + n/2 - cur*/n-cur << endl;
return 0 ;
}
/*
6
1 3 5 5 7 9
*/ 标准的SET的AC代码（233ms）：
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int a[1000005];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n);
multiset<int> se;
for (int i = n / 2; i < n; i++) {
se.insert(a[i]);
}
int ans = n;
for (int i = 0; i < n / 2; i++) {
multiset<int>::iterator it = se.lower_bound(a[i] * 2);
if (it == se.end()) break;
se.erase(it);
ans--;
}
printf("%d\n", ans);
return 0;
}
另一个线性的做法（不用SET的标程82ms）：
#include <algorithm>
#include <cstdio>
using namespace std;
int a[500005];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n);
int ans = n, pos = n / 2;
for (int i = 0; i < n / 2; i++) {
while (pos < n && a[pos] < a[i] * 2) pos++;
if (pos == n) break;
ans--;
pos++;
}
printf("%d\n", ans);
return 0;
}
这题还可以二分：
后来就想到，如果某种方案配对了x对，那么我们可以统一将这x对中比较大的数字，从大到小依次用a[n],a[n-1]……a[n-x+1]给替换掉；而比较小的数字从小到大依次用a[1]……a[x]替换掉，可知替换出来还是满足条件的方案。另外我们将每一对视作一条边，连接小数字的有序数列和大数字的有序数列，那么会产生一个二分图。
如果两条边出现交叉，也就是出现a[i]<a[j], a[ii]>a[jj]，a[i]*2<=a[ii]，a[j]*2<=a[jj]。那么可以将i连接jj而j连接ii。经过一阵重新连接，我们发现，可能的方案等价于a[1]连接a[n-x+1]……a[x]连接a[n]，于是现在我们只需要找出具体对于哪个x成立就行了，所以对于这种，已知答案就可以推算是否合理的题目，我们选择二分。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 6e5 + 5;
int a[MAX],n;
bool ok(int x) {
for(int i = 1; i<=x; i++) {
if(a[i+n-x]<a[i]*2) return 0;
}
return 1;
}
int main()
{
cin>>n;
for(int i = 1; i<=n; i++) scanf("%d",a+i);
sort(a+1,a+n+1);
int l=0,r=n/2,mid,ans=0;
while(l<=r){
mid = (l+r)>>1;
if(ok(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d",n-ans);
return 0;
}
京公网安备 11010502036488号