[BOI2010 bins]一个桶

【BOI链接】http://www.ut.ee/boi/
【题目大意】
按顺序给出n<=20000个箱子，他们的尺寸m<=1000。
求一个最大的k，使得前k个和第k+1个到2*k个箱子之间能一一匹配。
能匹配的定义是i∈[1,k] 且 j∈[k+1,2*k] 同时Size[i]【算法分析】
因为m<=1000，开一个1000的桶，然后从k从n/2开始枚举下来，维护一下。
由于O(nm)都不会超时，直接每次都暴力判断就好了。
【CODE】
#include #include #include int a[20001],t1[1001],t2[1001];

bool flag(){
int num1=0,num2=0,i;
for (i=1;i<=m;i++){
if (num1 num1+=t1[i];
num2+=t2[i];
if (num1 }
return true;
}

int main(){
int i,k,ans=0;
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
freopen("bins.in","r",stdin);
freopen("bins.out","w",stdout);
scanf("%d%d",&m,&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
k=n/2;
for (i=1;i<=k;i++) t1[a[i]]++;
for (i=k+1;i<=2*k;i++) t2[a[i]]++;
for (k=n/2;k>=0;k–){
if (flag()){
ans=k;
break;
}
if (!k) break;
t1[a[k]]–;
t2[a[k]]++;
t2[a[2*k]]–;
t2[a[2*k-1]]–;
}
printf("%dn",ans);
}