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

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

Решение

Отсортируем исходные данные в двухмерном массиве a по времени прибытия на парковку (в программах на PascalABC и C++ использован алгоритм сортировки выбором). Последовательно обрабатывая информацию об автомобилях, будем выбирать наименьшую подходящую категорию и помещать информацию о времени освобождения парковочного места в двухмерный массив b, где первым элементом является время освобождения, а вторым - категория места. Переменная nb хранит фактическое количество данных в массиве. Перед помещением каждого нового автомобиля в массив b, будем удалять из него все автомобили, которые должны были покинуть парковку к прибытию обрабатываемого автомобиля. В данном решении массив b отсортирован по времени в порядке убывания. Место вставки новых данных ищется бинарным поиском. Таким образом, удаляемые данные всегда расположены в конце массива и на их удаление не нужно тратить время, а достаточно просто уменьшить счетчик nb. Такое решение сложнее, но более эффективно для большого количества данных. Вариант решения без оптимизации работы с массивом b приведен в Задаче 6412. Помимо указанных двух массивов, в программе используются следующие одномерные массивы:
total - общее количество мест по категориям;
busy - количество занятых в данный момент мест в категориях;
count - общее количество машин, припарковавшихся в каждой категории;
time - время освобождения всех парковочных мест для каждой категории.

Python

f = open('26-120.txt')
m, n = map(int, f.readline().split())
total = [int(x) for x in f.readline().split()]
busy = [0] * m
count = [0] * m
time = [0] * m
a = [[int(y) for y in x.split()] for x in f]
a.sort()
b = []
for i in a:
    j = len(b) - 1
    while j > -1 and b[j][0] <= i[0]:
        busy[b[j][1]] -= 1
        del b[j]
        j -= 1
    if len(b) == 0:
        right = 0
    else:
        left = -1
        right = len(b)
        while left != right - 1:
            center = (left + right) // 2
            if b[center][0] <= i[0] + i[1]:
                right = center
            else:
                left = center
    category = -1
    for j in range(i[2], m):
        if total[j] > busy[j]:
            category = j
            break
    if category != - 1:
        b.insert(right, [i[0] + i[1], category])
        busy[category] += 1
        count[category] += 1
        time[category] = max(time[category], i[0] + i[1])
mx = 0
for i in range(1, m):
    if count[i] > count[mx]:
        mx = i
print(time[mx], count[mx])

PascalABC

var
    n, m, i, j, nb, t, right, left, center, category, min, max: Integer;
    a: array [1..900, 1..3] of Integer;
    b: array [1..900, 1..2] of Integer;
    total, busy, count, time: array [0..5] of Integer;
    f: TEXT;
begin
    Assign(f, '26-120.txt');
    Reset(f);
    Readln(f, m, n);
    for i := 0 to m - 1 do
    begin
        Read(f, total[i]);
        busy[i] := 0;
        count[i] := 0;
        time[i] := 0;
    end;
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2], a[i, 3]);
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n do
            if a[j, 1] < a[min, 1] 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;
            t := a[i, 3];
            a[i, 3] := a[min, 3];
            a[min, 3] := t;
        end;
    end;
    nb := 0;
    for i := 1 to n do
    begin
        for j := nb downto 1 do
            if b[j, 1] <= a[i, 1] then
            begin
                busy[b[j, 2]] := busy[b[j, 2]] - 1;
                nb := nb - 1
            end
            else
                break;
        if nb = 0 then
            right := 1
        else
        begin
            left := 0;
            right := nb + 1;
            while left <> right - 1 do
            begin
                center := (left + right) div 2;
                if b[center, 1] <= a[i, 1] + a[i, 2] then
                    right := center
                else
                    left := center
            end;
        end;
        category := -1;
        for j := a[i, 3] to m - 1 do
            if total[j] > busy[j] then
            begin
                category := j;
                break;
            end;
        if category <> -1 then
        begin
            for j := nb downto right do
            begin
                b[j + 1, 1] := b[j, 1];
                b[j + 1, 2] := b[j, 2];
            end;
            nb := nb + 1;
            b[right, 1] := a[i, 1] + a[i, 2];
            b[right, 2] := category;
            busy[category] := busy[category] + 1;
            count[category] := count[category] + 1;
            if a[i, 1] + a[i, 2] > time[category] then
                time[category] := a[i, 1] + a[i, 2];
        end;
    end;
    max := 0;
    for i := 0 to m - 1 do
        if count[i] > count[max] then
            max := i;
    Writeln(time[max], ' ', count[max]);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-120.txt");
    int m, n;
    f >> m >> n;
    int total[6], busy[6], count[6], time[6];
    int a[900][3], b[900][2];
    for (int i = 0; i < m; i++)
    {
        f >> total[i];
        busy[i] = 0;
        count[i] = 0;
        time[i] = 0;
    }
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][1] >> a[i][2];
    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])
                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;
            t = a[i][2];
            a[i][2] = a[min][2];
            a[min][2] = t;
        }
    }
    int nb = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = nb - 1; j >= 0; j--)
            if (b[j][0] <= a[i][0])
            {
                busy[b[j][1]]--;
                nb--;
            }
            else
                break;
        int left, right, center;
        if (nb == 0)
            right = 0;
        else
        {
            left = -1;
            right = nb;
            while (left != right - 1)
            {
                center = (left + right) / 2;
                if (b[center][0] <= a[i][0] + a[i][1])
                    right = center;
                else
                    left = center;
            }
        }
        int category = -1;
        for (int j = a[i][2]; j < m; j++)
            if (total[j] > busy[j])
            {
                category = j;
                break;
            }
        if (category != -1)
        {
            for (int j = nb - 1; j >= right; j--)
            {
                b[j + 1][0] = b[j][0];
                b[j + 1][1] = b[j][1];
            }
            nb++;
            b[right][0] = a[i][0] + a[i][1];
            b[right][1] = category;
            busy[category]++;
            count[category]++;
            if (a[i][0] + a[i][1] > time[category])
                time[category] = a[i][0] + a[i][1];
        }
    }
    int max = 0;
    for (int i = 1; i < m; i++)
        if (count[i] > count[max])
            max = i;
    cout << time[max] << " " << count[max] << endl;
}

Ответ

194534 140

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