一个很简单的题;
方法一:
二分。
代码:
#include<cstdio>
#include<algorithm>
#define maxn 100005
using namespace std; int num[maxn],n; int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&num[i]);
sort(num,num+n);
int ans=;
for(int i=;i<n;i++)
{
int x=upper_bound(num,num+n,*num[i])-num-i;
if(ans<x)ans=x;
}
printf("%d\n",n-ans);
return ;
}
方法二:
双端队列;
代码:
#include<cstdio>
#include<algorithm>
#include<queue>
#define maxn 100005
using namespace std; int num[maxn],n;
queue<int>q; int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&num[i]);
sort(num,num+n);
int ans=;
for(int i=;i<n;i++)
{
q.push(num[i]);
if(q.front()*<q.back())q.pop();
if(ans<q.size())ans=q.size();
}
printf("%d\n",n-ans);
return ;
}