Codeforces Round #154 (Div. 2) : B

一个很简单的题；

方法一：

二分。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define maxn 100005
 4 using namespace std;
 5 
 6 int num[maxn],n;
 7 
 8 int main()
 9 {
10     freopen("input.txt", "r", stdin);
11     freopen("output.txt", "w", stdout);
12     scanf("%d",&n);
13     for(int i=0;i<n;i++)scanf("%d",&num[i]);
14     sort(num,num+n);
15     int ans=0;
16     for(int i=0;i<n;i++)
17     {
18         int x=upper_bound(num,num+n,2*num[i])-num-i;
19         if(ans<x)ans=x;
20     }
21     printf("%d
",n-ans);
22     return 0;
23 }

View Code

方法二：

双端队列；

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #define maxn 100005
 5 using namespace std;
 6 
 7 int num[maxn],n;
 8 queue<int>q;
 9 
10 int main()
11 {
12     freopen("input.txt", "r", stdin);
13     freopen("output.txt", "w", stdout);
14     scanf("%d",&n);
15     for(int i=0;i<n;i++)scanf("%d",&num[i]);
16     sort(num,num+n);
17     int ans=0;
18     for(int i=0;i<n;i++)
19     {
20         q.push(num[i]);
21         if(q.front()*2<q.back())q.pop();
22         if(ans<q.size())ans=q.size();
23     }
24     printf("%d
",n-ans);
25     return 0;
26 }

View Code