Решение задачи Большой отрезок с Codeforces

С пояснением   Просмотров: 1322

На координатной прямой задано n отрезков, i-ый отрезок начинается в позиции l i и заканчивается в позиции r i. Будем обозначать такой отрезок через [l i, r i].

Вы предположили, что один из заданных отрезков покрывает все остальные. Другими словами, существует такой отрезок из заданного набора, в котором содержатся все остальные. Теперь вы хотите убедиться в своем предположении. Найдите отрезок из набора, который покрывает все остальные заданные отрезки, и выведите его номер. Если такого отрезка не существует, выведите -1.

Формально будем считать, что отрезок [a, b] покрывает отрезок [c, d], если выполняется условие a ≤ c ≤ d ≤ b.

Код 

#include<bits/stdc++.h>

using namespace std;

int n,st = 0x3f3f3f3f,ed = 0,f[100100],s[100100];

int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> f[i] >> s[i];
		st = min(f[i],st);
		ed = max(s[i],ed); 
	}
	for(int i = 0;i < n;i++)
		if(f[i] <= st && s[i] >= ed)
			cout << i+1,exit(0);
	cout << "-1";
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Для начала заметим, что ответ всегда однозначный, потому что если существует отрезок номер i, который покрывает отрезок номер j, то отрезок j никак не может покрывать отрезок i. Единственный случай, когда такое возможно, — это когда отрезки i и j совпадают, однако по условию в наборе нет одинаковых отрезков. Заметим, что ответ должен покрывать самую левую из всех точек всех отрезков, и аналогично, самую правую из всех точек. Таким образом, надо найти эти точки линейным проходом: L = min(l i), R = max(r i), и найти номер отрезка [L, R], либо вывести  - 1, если его нет в заданном множестве. Время --– O(n).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp