caozy623's Blog

题意：

有一些袋鼠，将A袋鼠装进B的口袋当且仅当Va*2<=Vb，每只袋鼠只能装一只。问最少可以剩下多少袋鼠能被看到。（就是说装进口袋里就看不见了）

这道题也能作为div1 A……挺水的，只需要sort一下然后贪心即可，因为最少只能是[n/2]+1。所以从i从n/2枚举到1，j从n开始枚举到n/2+1。然后简单贪心一下即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 1000010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
#define REP( i, n ) for ( int i = 1; i <= n; i ++ )
#define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
#define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
#define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
#define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
#define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
#define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
#define RST( a ) memset ( a, 0, sizeof ( a ) )
#define CLR( a, x ) memset ( a, x, sizeof ( a ) )
#define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int n;
int a[maxn];
int main()
{
    n=read();
    REP(i,n) a[i]=read();
    sort(a+1,a+n+1);
    int j=n;
    int ans=n;
    DWN(i,1,(n/2))
    if(a[i]*2<=a[j])
    {
        ans--;
        j--;
    }
    printf("%d\n",ans);
    return 0;
}