Задача 6792. Источник: Поляков. Задание КИМ 26

Страница задачи 6792

Решение

Считаем данные в двухмерный массив/список и отсортируем по времени входа в магазин, а при равенстве времени входа, по времени выхода. В переменной shop будем сохранять время выхода посетителей, находящихся в магазине. Размер данного списка/массива/вектора и является количеством людей, находящихся в магазине одновременно. Последовательно обрабатываем отсортированный список данных. Удаляем из shop всех покупателей, которые покинули магазин до визита обрабатываемого посетителя, добавляем информацию о новом посетителе и анализируем список на максимальный размер. Чтобы обнаружить другой пик с максимальным количеством покупателей, в переменной last будем сохранять последний размер shop. Новый пик засчитывается, если в last значение меньше максимального.

Python

f = open('26-130.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
kmx = 0
mx = 0
last = 0
shop = []
for i in a:
    j = 0;
    while j < len(shop):
        if shop[j] < i[0]:
            del shop[j]
        else:
            j += 1
    shop.append(i[1])
    if len(shop) > mx:
        mx = len(shop)
        kmx = 1
    elif len(shop) == mx and last != mx:
        kmx += 1
    last = len(shop)
print(kmx, mx)

PascalABC

var
    n, max, min, kmax, last, i, j, t: Integer;
    a: array [1..987, 1..2] of Integer;
    shop: array of Integer = new Integer[0];
    f: TEXT;
begin
    Assign(f, '26-130.txt');
    Reset(f);
    Readln(f, n);
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2]);
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n do
            if (a[j, 1] < a[min, 1]) or (a[j, 1] = a[min, 1]) and (a[j, 2] < a[min, 2]) then
                min := j;
        if min <> i then
        begin
            t := a[i, 1];
            a[i, 1] := a[min, 1];
            a[min, 1] := t;
            t := a[i, 2];
            a[i, 2] := a[min, 2];
            a[min, 2] := t;
        end;
    end;
    max := 0;
    kmax := 0;
    last := 0;
    for i := 1 to n do
    begin
        j := 0;
        while j < shop.Length do
            if shop[j] < a[i, 1] then
                shop := shop[:j] + shop[j + 1:]
            else
                j := j + 1;
        shop := shop + Arr(a[i, 2]);
        if shop.Length > max then
        begin
            max := shop.Length;
            kmax := 1;
        end
        else if (shop.Length = max) and (last <> max) then
            kmax := kmax + 1;
        last := shop.Length;
    end;
    Writeln(kmax, ' ', max);
end.

C++

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-130.txt");
    int n;
    f >> n;
    int a[987][2];
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][1];
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j][0] < a[min][0] || a[j][0] == a[min][0] && a[j][1] < a[min][1])
                min = j;
        if (min != i)
        {
            int t = a[i][0];
            a[i][0] = a[min][0];
            a[min][0] = t;
            t = a[i][1];
            a[i][1] = a[min][1];
            a[min][1] = t;
        }
    }
    vector<int> shop;
    int max = 0, kmax = 0, last = 0;
    for (int i = 0; i < n; i++)
    {
        int j = 0;
        while (j < shop.size())
            if (shop[j] < a[i][0])
                shop.erase(shop.begin() + j);
            else
                j++;
        shop.push_back(a[i][1]);
        if (shop.size() > max)
        {
            max = shop.size();
            kmax = 1;
        }
        else if (shop.size() == max && last != max)
            kmax++;
        last = shop.size();
    }
    cout << kmax << " " << max << endl;
}

Ответ

1 644

Отправить замечание по решению