GitBook

这里写图片描述

给n个袋鼠以及对应大小,把较小的放到较大的口袋里,判断最后头在外面的松鼠最少多少只

能放在里面的条件是 a[i]*2<=a[j] 先把数组按照从小到大排序 若想让外面有x个 则a[0]~a[n-x]必然要被装 所以可以以此判断 进行二分查找

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[500200];
int n;
bool judge(int x) {
	if(x<(n+1)/2)
		return false;
	for(int i=0; i<n-x; i++) {
		if(a[i]*2>a[i+x])
			return false;
	}
	return true;
}
int main() {
	while(scanf("%d",&n)!=EOF) {
		for(int i=0; i<n; i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		int l=1,r=n,res;
		while(l<=r) {
			int mid=(l+r)/2;
			if(judge(mid)) {
				res=mid;
				r=mid-1;
			} else
				l=mid+1;
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【CodeForces】[372A]Counting Kangaroos is Fun