题解 P6807 【[BalticOI 2010 Day2] Matching Bins】

· · 题解

我第一眼看到这个题时，立马就想到了暴力。

枚举 k ，把前 k 个数和接下来 k 个数从小到大排序然后一一比大小，出现前面 k 个里的第几个数大于等于后面 k 个里的第几个数就排除掉。

然后想到优化：

  1. 从后往前枚举，最先找到的正确的那个就是答案。

  3. 既然给了 m 那就一定是有用的，记录下最早的那个 m , k 值一定是比这个 m 所在序号小的，因为后面不可能到比最大值还大的数。

  4. 用桶排。 sort 一定是会炸的。

就下来就是代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int m,n,ji=1000000000,f[20010],fa[2010],fb[2010],chu,o;
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
int check(int x){
    int oo=1;
    for(int i=1;i<=x;i++)
        fa[f[i]]+=1;
    for(int i=x+1;i<=2*x;i++)
        fb[f[i]]+=1;
    int a=1,b=1;
    for(int i=1;i<=x;i++){
        while(!fa[a])a++;
        while(!fb[b])b++;
        if(a>=b)oo=0;
        fa[a]--;
        fb[b]--;
    }
    return oo;
}
int main(){
    m=read();
    n=read();
    for(int i=1;i<=n;i++){
        f[i]=read();
        if(f[i]==m&&o==0){
            o=1;
            ji=i;
        }
    }
    ji=min(ji-1,n/2);
    for(int i=ji;i>=1;i--)
        if(check(i)){
            chu=i;
            break;
        }
    cout<<chu;
    return 0;
}