[ccAUG14] Cleaning Tables

描述 Description

Haku has been newly hired by Chef to clean tables at his restaurant. So whenever a customer wants a table, Haku must clean it.

But Haku happens to be a lazy boy. So in the morning, when the restaurant is opened, all the tables are dirty from night before.

The customer don’t leave the table unless they are politely requested to do so. And customers can order meal later again. So if they were already having a table, they can be served on the same table [Haku doesn’t have to clean :)]. But if they don’t have a table then they must be given some table [Haku must clean :(]

The restaurant has N tables. When a customer requires a table, he/she can occupy any unoccupied table. However if all tables are occupied, then Haku is free to ask politely any customer to leave his/her table. And the freed table can be given to the waiting customer.

Now Chef has the psychic ability to tell the order of customer meal requests for the entire day. Given this list, help Haku find the minimum number of times he has to clean the tables.

输入格式 InputFormat

First line contains integer T, number of test cases.

First line of each test case contains 2 integers N, number of tables and M, number of customer orders. Followed by M integers on next line, which is the order in which customers ask for meal. Customers are referenced by integer C.

输出格式 OutputFormat

For each test case output the minimum number of times Haku must clean the table(s).

样例输入 SampleInput

4
2 4
1 2 3 4
3 2
4 1
3 6
1 2 1 3 4 1
3 5
1 2 1 3 4

样例输出 SampleOutput

4
2
4
4

CodeChef CLETAB

贪心，如果桌子未满直接加，如果已满则下一次最迟出现的那一桌的顾客。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int T;
pair <int,int> a[405],f[405];
int c[405],inq[405];
int ans;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        for (i=0;i<=400;i++) c[i]=405;
        memset(inq,0,sizeof(inq));
        memset(f,0,sizeof(f));
        ans=0;
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;i++) scanf("%d",&a[i].first);
        for (i=m;i>0;i--) a[i].second=c[a[i].first],c[a[i].first]=i;
        x=0;
        for (i=1;i<=m;i++)
        {
            if (!inq[a[i].first])
            {
                ans++;
                if (x<n)
                {
                    f[++x]=a[i];
                    inq[f[x].first]=x;
                }
                else
                {
                    t=1;
                    for (j=2;j<=x;j++) if (f[t].second<f[j].second) t=j;
                    inq[f[t].first]=0;f[t]=a[i];inq[f[t].first]=t;
                }
            }
            else
            {
                f[inq[a[i].first]]=a[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}