CF 253B(队列下维护2个指针后移)

CF 253B(队列上维护2个指针后移)
B. 实验误差time limit per test1 secondmemory limit per test256 megabytesinputinput.txtoutputoutput.txt

小明做实验，测了n次结果，因为误差，这些结果不一样。

至少修改多少结果，才能使最大的结果不超过最小的结果的2倍？

第一行一个整数 n (2?≤?n?≤?10^{5)，第二行有n个数c_{1,?c2,?...,?cn表示结果(1?≤?ci?≤?5000)}}

输出一个整数，表示最小修改次数。

64 5 3 8 3 7

2

44 3 2 4

0

第1个数据删除8，7，第二个数据本身就满足条件。

排序，从小到大枚举最小数，并把后指针挪向最大的不用修改的数进行统计即可。

#include<cstdio>#include<functional>#include<algorithm>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;#define MAXN (100000+100)int a[MAXN];int n;int main(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);a[n+1]=1000000;//for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;int t=1,ans=0;for (int h=1;h<=n;h++){while (a[h]*2>=a[t+1]) t++;ans=max(ans,t-h+1);}cout<<n-ans<<endl;}