790. Двойная очередь

 

Недавно образованная Балканская Инвестиционная Банковская Группа (БИГ-Банк) открыла новый офис в Бухаресте, оснащенный современной вычислительной техникой, предоставленной компанией IBM Румыния, с использованием современных информационных технологий. Как правило, каждый клиент банка идентифицируется натуральным числом k. По приходу в банк за получением услуг, он или она получает некоторое натуральное число – приоритет p. Одно из изобретений молодых менеджеров банка шокировало инженера программного обеспечения по обслуживанию системы. Они решили сломать традицию, предложив обслуживать первым клиента не только с наибольшим приоритетом, но и с наименьшим. Известно, что система на вход получает следующие типы запросов:

   0      Система обслуживания клиентов останавливается

1 k p   Добавить клиента k с приоритетом p в список ожидания

   2      Обслужить клиента с наибольшим приоритетом и удалить из списка ожидания

   3      Обслужить клиента с наименьшим приоритетом и удалить из списка ожидания

Вам следует помочь инженеру программного обеспечения банка, написав программу обслуживания клиентов согласно указанному принципу.

 

Вход. Каждая входная строка содержит один из возможных запросов; только последняя строка содержит требование остановить работу системы (код 0). Если приходит запрос на включение клиента в очередь (код 1), то считайте, что других запросов по этому клиенту, или по клиенту с таким же приоритетом на данный момент не существует. Значение  k всегда меньше 106, а приоритет p меньше 107. Клиент может приходить и обслуживаться несколько раз, каждый раз получая разное значение приоритета.

 

Выход. Для каждого запроса с кодом 2 или 3 программа должна вывести в отдельной строке идентификатор обслуженного клиента. Если поступает запрос при пустой очереди на обслуживание, то следует вывести ноль (0).

 

Пример входа

Пример выхода

2

1 20 14

1 30 3

2

1 10 99

3

2

2

0

0

20

30

10

0

 

РЕШЕНИЕ

структуры данных - set

 

Анализ алгоритма

Приоритеты клиентов будем хранить во множестве s. Тогда клиент с наименьшим приоритетом будет находиться в начале множества, а с наибольшим в конце. Поскольку приоритеты всех клиентов разные, можно установить взаимно однозначное соответствие между приоритетом и номером клиента. Будем хранить их в парах (приоритет, номер клиента).

Для решения задачи достаточно промоделировать процесс обслуживания клиентов.

 

Реализация алгоритма

Приоритеты и номера клиентов, находящихся в очереди, будем хранить во множестве пар s. Если на обслуживание поступает клиент с номером k и приоритетом p, то во множество s заносим пару (p, k).

 

set<pair<int,int> > s;

 

Основная часть программы. В зависимости от типа запроса производим соответствующее действие. Продолжаем цикл, пока система обслуживания клиентов не остановится (значение code не станет равным 0).

 

while(scanf("%d",&code), code)

 

Заносим приоритет и номер поступившего клиента во множество s.

 

  if (code == 1)

  {

    scanf("%d %d",&k,&p);

    s.insert(make_pair(p,k));

  } else

 

Наибольший приоритет клиента находится в конце множества s.

 

  if (code == 2)

    if (s.empty()) printf("0\n"); else

    {

      iter = s.end(); iter--;

      printf("%d\n",(*iter).second);

      s.erase(iter);

  } else

 

Наименьший приоритет клиента находится в начале множества s.

 

   if (s.empty()) printf("0\n"); else

   {

     printf("%d\n",(*s.begin()).second);

     s.erase(s.begin());

   }

 

Реализация алгоритма – set of integers

 

#include <cstdio>

#include <set>

using namespace std;

 

set<int> s;

set<int>::iterator iter;

int client[10000001];

int code, k, p;

 

int main(void)

{

  while (scanf("%d", &code), code)

    if (code == 1)

    {

      scanf("%d %d", &k, &p);

      client[p] = k; s.insert(p);

    }

    else

    if (code == 2)

      if (s.empty()) printf("0\n"); else

      {

        iter = s.end(); iter--;

        printf("%d\n", client[*iter]);

        s.erase(iter);

      }

    else

      if (s.empty()) printf("0\n"); else

      {

        printf("%d\n", client[*s.begin()]);

        s.erase(s.begin());

      }

  return 0;

}

 

Java реализация BufferReader = 1,2sec

 

import java.util.*;

import java.io.*;

 

public class Main

{

  public static void main(String[] args)

  throws Exception

  {

    BufferedReader in =

      new BufferedReader(new InputStreamReader(System.in));

    int[] Client = new int[10000001];

    int Code;

    TreeSet<Integer> s = new TreeSet<Integer>();

    String Line;

    while(!(Line = in.readLine()).equals("0"))

    {

      StringTokenizer st = new StringTokenizer(Line);

      Code = Integer.parseInt(st.nextToken());

      if (Code == 1)

      {

        int k = Integer.parseInt(st.nextToken()),

            p = Integer.parseInt(st.nextToken());

        Client[p] = k; s.add(p);

      } else

      if (Code == 2)

      if (s.isEmpty()) System.out.println("0"); else

      {

         int LastElement = s.last();

         System.out.println(Client[LastElement]);

         s.remove(LastElement);

      } else

      if (s.isEmpty()) System.out.println("0"); else

      {

        int FirstElement = s.first();

        System.out.println(Client[FirstElement]);

        s.remove(FirstElement);

      }

    }

  }

}

 

Java реализация Scanner = 1,4 sec

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int[] Client = new int[10000001];

    int Code;

    TreeSet<Integer> s = new TreeSet<Integer>();

    while((Code = con.nextInt()) != 0)

    {

      if (Code == 1)

      {

        int k = con.nextInt(), p = con.nextInt();    

        Client[p] = k; s.add(p);

      } else

      if (Code == 2)

      if (s.isEmpty()) System.out.println("0"); else

      {

         int LastElement = s.last();

         System.out.println(Client[LastElement]);

         s.remove(LastElement);

      } else

      if (s.isEmpty()) System.out.println("0"); else

      {

        int FirstElement = s.first();

        System.out.println(Client[FirstElement]);

        s.remove(FirstElement);

      }

    }

  }

}

 

Java реализация FastScanner = 1 sec

 

import java.util.*;

import java.io.*;

 

class FastScanner

{

  private BufferedReader br;

  private StringTokenizer st;

 

  public FastScanner(InputStreamReader reader)

  {

    br = new BufferedReader(reader);

  }

 

  public String next()

  {

    while (st == null || !st.hasMoreTokens())

    {

      try

      {

        st = new StringTokenizer(br.readLine());

      } catch (Exception e)

      {

        e.printStackTrace();

      }

    }

    return st.nextToken();

  }

 

  public int nextInt()

  {

    return Integer.parseInt(next());

  }

 

  public double nextDouble()

  {

    return Double.parseDouble(next());

  }

 

  public void close() throws Exception

  {

    br.close();

  }

}

 

public class Main

{

  public static void main(String[] args)

  {

    FastScanner con =

      new FastScanner(new InputStreamReader(System.in));   

    int[] Client = new int[10000001];

    int Code;

    TreeSet<Integer> s = new TreeSet<Integer>();

    while((Code = con.nextInt()) != 0)

    {

      if (Code == 1)

      {

        int k = con.nextInt(), p = con.nextInt();    

        Client[p] = k; s.add(p);

      } else

      if (Code == 2)

      if (s.isEmpty()) System.out.println("0"); else

      {

         int LastElement = s.last();

         System.out.println(Client[LastElement]);

         s.remove(LastElement);

      } else

      if (s.isEmpty()) System.out.println("0"); else

      {

        int FirstElement = s.first();

        System.out.println(Client[FirstElement]);

        s.remove(FirstElement);

      }

    }

  }

}

 

Java реализация – TreeMap

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();   

    while(true)

    {

      int Code = con.nextInt();

      if (Code == 0) break;

      if (Code == 1)

      {

        int k = con.nextInt();

        int p = con.nextInt();

        tree.put(p,k);

      } else

      if (Code == 2)

        if (tree.isEmpty()) System.out.println("0"); else

        {

         System.out.println(tree.lastEntry().getValue());

         tree.pollLastEntry();

      } else

      if (tree.isEmpty()) System.out.println("0"); else

      {

        System.out.println(tree.firstEntry().getValue());

        tree.pollFirstEntry();

      }

    }

    con.close();

  }

}