Codeforces Round #154 (Div. 2) : B

一个很简单的题;

方法一:

二分。

代码:

 #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 ;
}
上一篇:五种实用DOM方法总结


下一篇:javascript动画效果之多物体透明度