Задача 7109. Источник: Поляков. Задание КИМ 26
(PRO100-ЕГЭ) Входной файл содержит расписание показа фильмов во всех кинотеатрах Москвы за весь прошедший месяц. Определите суммарное время, в течение которого показывался хотя бы один фильм.
Входные данные представлены в файле 26-140.txt следующим образом. В первой строке входного файла находится натуральное число N (N ≤ 1000) – общее количество фильмов. Следующие N строк содержат пары натуральных чисел, обозначающих время начала и время окончания каждого фильма в минутах с начала месяца. Все числа не превосходят 44640.
Запишите в ответе два числа: суммарное время (в минутах), в течение которого показывался хотя бы один фильм и максимальную длину непрерывного отрезка времени (в минутах), в течение которого показывался хотя бы один фильм.
Пример входного файла:
4
100 200
200 250
400 500
420 480
При таких исходных данных хотя бы один фильм показывался в промежутки времени [100; 250) и [400; 500). Суммарное время равно (250-100) + (500-400) = 250. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен 250-100 = 150. Ответ: 250 150.
Решение
Сортируем исходные данные по возрастанию времени начала фильма, а, при равенстве времени начала, по убыванию времени окончания. В переменной start будем хранить время начала текущего непрерывного периода, last - время окончания последнего фильма, total - общее время, когда показывался хотя бы один фильм, max (mx) - максимальный непрерывный интервал, когда показывался хотя бы один фильм. Последовательно обрабатываем отсортированные данные. Если время начала очередного фильма больше времени окончания последнего фильма, то непрерывный период прервался и start и last меняют значение на время начала текущего фильма. Если время окончания текущего фильма больше времени окончания последнего, то к total прибавляем разницу между временем окончания текущего фильма и last, значение last меняется на время окончания текущего фильма, а разницу между last и start (длину текущего непрерывного промежутка) анализируем на максимальность. После обработки всех данных, выводим результат.
Python
f = open('26-140.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[1], reverse=True)
a.sort(key=lambda x: x[0])
start = 0
last = 0
total = 0
mx = 0
for i in a:
if i[0] > last:
start = i[0]
last = i[0]
if i[1] > last:
total += i[1] - last
last = i[1]
mx = max(mx, last - start)
print(total, mx)
PascalABC
var
n, start, total, max, last, min, i, j, t: Integer;
a: array [1..10000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-140.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;
start := 0;
last := 0;
total := 0;
max := 0;
for i := 1 to n do
begin
if a[i, 1] > last then
begin
start := a[i, 1];
last := a[i, 1];
end;
if a[i, 2] > last then
begin
total := total + a[i, 2] - last;
last := a[i, 2];
if last - start > max then
max := last - start;
end;
end;
Writeln(total, ' ', max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-140.txt");
int n;
f >> n;
int a[10000][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;
}
}
int start = 0, last = 0, total = 0, max = 0;
for (int i = 0; i < n; i++)
{
if (a[i][0] > last)
{
start = a[i][0];
last = a[i][0];
}
if (a[i][1] > last)
{
total += a[i][1] - last;
last = a[i][1];
if (last - start > max)
max = last - start;
}
}
cout << total << " " << max << endl;
}
Ответ
38032 3014