Codeforces Round 219 Div1A. Counting Kangaroos is Fun
問題
n頭(?)のカンガルーがいて、それぞれサイズがs[i]です。
カンガルーは以下の条件を満たすとき、別のカンガルーのポケットに入れます。
- (入る側のカンガルーのサイズ)*2≦(入られる側のカンガルーのサイズ)
- 入る側にも入られる側にも、別のカンガルーが入っていない
ポケットに入っていないカンガルー(別のカンガルーをポケットに入れているカンガルーも含む)は最少で何頭になるでしょうか。
制約
1≦n≦500000
1≦s[i]≦100000
解法
どう頑張ってもn/2頭までしか減らないので、大きいほう半分は一方的に入られる側で、
小さい方半分は一方的に入る側だと考えることができます。
よって、サイズが大きい方から順に「小さい方半分の中で、自分のポケットに入れる一番サイズがでかいやつ」を入れていくという方針で大丈夫そうです。
プログラム
#include<iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #define _USE_MATH_DEFINES #include <math.h> #include<string> #include<vector> #include<cmath> #include<stack> #include<queue> #include<sstream> #include<algorithm> #include<map> #include<complex> #include<ctime> #include<set> using namespace std; #define li long long int #define rep(i,to) for(li i=0;i<((li)(to));i++) #define repp(i,start,to) for(li i=(li)(start);i<((li)(to));i++) #define pb push_back #define sz(v) ((li)(v).size()) #define bgn(v) ((v).begin()) #define eend(v) ((v).end()) #define allof(v) (v).begin(), (v).end() #define dodp(v,n) memset(v,(li)n,sizeof(v)) #define bit(n) (1ll<<(li)(n)) #define mp(a,b) make_pair(a,b) #define rin rep(i,n) #define EPS 1e-10 #define ETOL 1e-8 #define MOD 100000000 #define F first #define S second #define p2(a,b) cout<<a<<"\t"<<b<<endl #define p3(a,b,c) cout<<a<<"\t"<<b<<"\t"<<c<<endl li a[500500]; int main(){ li n; cin>>n; rin{cin>>a[i];} sort(a,a+n); li res=n; li b=n-1; rep(i,n/2){ if(a[n/2-i-1]*2<=a[b]){ res--; b--; } } cout<<res<<endl; return 0; }