Задача 5606. Источник: Поляков. Задание КИМ 27
(К. Багдасарян) Администрация торговой площадки составила список зарегистрированных у нее N компаний с указанием их порядкового номера и рейтинга. Расстоянием между двумя компаниями будем считать разницу их порядковых номеров. Необходимо определить максимальное расстояние между двумя компаниями с номерами i, j (i < j), такими, что выполняются следующие условия:
- рейтинг компании с номером j больше рейтинга компании с номером i;
- между номерами i и j не существует компании, у которой рейтинг выше, чем у компании с номером i.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке число N (1 ≤ N ≤ 10 000 000) – количество компаний.
Каждая из следующих N строк содержит два натуральных числа: порядковый номер (не превышающее 10000000) и рейтинг компании (не превышающее 10000000).
Пример входного файла:
5
1 4
2 10
3 8
4 7
5 15
При таких исходных данных правильным ответом будет расстояние между компаниями с номерами 2 и 5: рейтинг компании № 5 больше рейтинга компании № 2, и между компаниями № 2 и № 5 нет компании с рейтингом, большим чем 10 (рейтинг компании № 2). Ответ: 3. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Загружаем исходные данные в массив. Просматривая массив с конца, ищем максимальный элемент, а от этого элемента ищем элемент, удовлетворяющий условию задачи, фиксируя максимальное расстояние. Переменные:
mxn - индекс максимального элемента с конца;
max (mx) - максимальное расстояние между парой, удовлетворяющей условию, т.е. ответ на задачу;
mxr - максимальный рейтинг, зафиксированный перед элементом с индексом mxn.
Python
f = open("27-126b.txt")
n = int(f.readline())
m = [[int(y) for y in x.split()] for x in f.readlines()]
mxn = n - 1
mx = 0;
mxr = 0
for i in range(n-2, -1, -1):
if m[i][1] < m[mxn][1] and m[i][1] >= mxr:
mx = max(mx, m[mxn][0] - m[i][0])
mxr = max(mxr, m[i][1])
if m[i][1] >= m[mxn][1]:
mxn = i
mxr = 0
print(mx)
PascalABC
var
n, i, mxn, mx, mxr: Integer;
m: array [1..100000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '27-126b.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
readln(f, m[i, 1], m[i, 2]);
mxn := n;
mx := 0;
mxr := 0;
for i := n - 1 downto 1 do
begin
if (m[i, 2] < m[mxn, 2]) and (m[i, 2] >= mxr) then
if m[mxn, 1] - m[i, 1] > mx then
mx := m[mxn, 1] - m[i, 1];
if m[i, 2] > mxr then
mxr := m[i, 2];
if m[i, 2] >= m[mxn, 2] then
begin
mxn := i;
mxr := 0;
end;
end;
writeln(mx);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-126b.txt");
int n;
f >> n;
int m[100000][2];
for (int i = 0; i < n; i++)
f >> m[i][0] >> m[i][1];
int mxn = n - 1, max = 0, mxr = 0;
for (int i = n - 2; i >= 0; i--)
{
if (m[i][1] < m[mxn][1] && m[i][1] >= mxr)
if (max < m[mxn][0] - m[i][0])
max = m[mxn][0] - m[i][0];
if (mxr < m[i][1])
mxr = m[i][1];
if (m[i][1] >= m[mxn][1])
{
mxn = i;
mxr = 0;
}
}
cout << max;
}
Ответ
253 725