51Nod 1420 数袋鼠好有趣

Problem

有n只袋鼠。每只袋鼠的大小用一个整数表示。一只小袋鼠能装进一只大袋鼠的条件是，大袋鼠的大小至少是小袋鼠的两倍。 每只大袋鼠最多可以装一只袋鼠。小袋鼠被装进大袋鼠之后就不能再装其它的袋鼠了。 小袋鼠被装进大袋鼠之后就不能被我们看见了。请找出一个装袋鼠的方案，使得被看见的袋鼠最少。

（袋鼠不能3只套在一起）

输出一个整数，即最少能看见的袋鼠数量。

Solution

排序，分成两半，前面和后面的匹配。一开始多了个等号一直错。

Code

#include<stdio.h>
#include<algorithm>
int n,a[500020],ans;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	std::sort(a+1,a+1+n);
	ans=n;
	int p1=1,p2=n/2+1;
	while(p1<=n/2&&p2<=n){
		while(p1<=n/2&&p2<=n&&a[p1]*2>a[p2]) p2++;
		if(p1<=n/2&&p2<=n){
			ans--;
		}
		p1++;
		p2++;
	}
	
	printf("%d\n",ans);
	return 0;
}