03 April 2015

UVA 12100 - Printer Queue (STL queue and deque)

#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int Maxn = 100+10;

int uni[Maxn];
int n, m;
int num[10];
int ma = 0;
struct node
{
    int id, rank;
} p[110];
queue<node> q;

void deal()
{
    while(!q.empty())
    {
        q.pop();
    }
}

int main(void)
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        deal();
        memset(num, 0, sizeof(num));
        scanf("%d %d",&n,&m);
        int tmp;
        node now, next;
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&tmp);
            ma = max(ma, tmp);
            p[i].id = i;
            p[i].rank = tmp;
            q.push(p[i]);
            num[tmp]++;
        }
        bool flag = false;
        int ans = 1;
        while(!flag)
        {
            while(1)
            {
                now = q.front() ;
                q.pop();
                if(now.rank == ma)
                {
                    ans++;
                    if(now.id == m)
                    {
                        flag = true;
                    }
                    num[ma]--;
                    while(num[ma]==0)
                    {
                        ma--;
                    }
                    break;
                }
                else
                    q.push(now);
            }
        }
        cout<<ans-1<<endl;

    }
    return 0;
}

No comments:

Post a Comment

UVA 10679 - I Love Strings!!