Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.04.2022, 14:28   #1
REZR
Пользователь
 
Регистрация: 05.04.2022
Сообщений: 26
По умолчанию Исправить ошибку.

На координатной прямой даны несколько отрезков с координатами [Li, Ri ]. Необходимо выбрать минимальное количество отрезков, которые бы полностью покрыли интервал [0, M ].

Входные данные: на первой строчке располагается число N, за которым следует N строк на каждой из которой находится пара чисел Li, Ri ; последняя строка содержит в себе число M .
Выходные данные: на первой строке число K выбранных отрезков, за которым следует K строк, содержащих в себе выбранные отрезки в том же порядке, в котом они встретились во входных данных. Если покрыть интервал невозможно, нужно распечатать число 0.

Код:
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Seq { int l, r, num; };

bool operator < (const Seq& a, const Seq& b)
{
	return (a.l < b.l) || ((a.l == b.l) && (a.r < b.r));
}

struct by_order
{
	bool operator() (const Seq& a, const Seq& b)
	{
		return a.num < b.num;
	}
};

int main()
{
	int n;
	cin >> n;
	vector<Seq> v;
	Seq s;
	for (int i = 0; i < n; i++)
		cin >> s.l >> s.r, s.num = i, v.push_back(s);
	sort(v.begin(), v.end());
	int m;
	cin >> m;
	set<Seq, by_order> st;
	int l = 0, r = 0;
	for (vector<Seq>::iterator it = v.begin(); it != v.end() && l < m; it++)
	{
		if (l >= it->r) continue;
		vector<Seq>::iterator max_right = it;
		while (l >= it->l && it != v.end())
		{
			if (it->r >= r) r = it->r, max_right = it;
			it++;
		}
		st.insert(*max_right);
		l = r;
		if (l >= it->l) it--;
	}
	if (l < m) { cout << 0 << endl; return 0; }
	cout << st.size() << endl;
	for (set<Seq>::iterator it = st.begin(); it != st.end(); it++)
		cout << it->l << " " << it->r << endl;
	return 0;
}
REZR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
С# Исправить ошибку Ladystrix Фриланс 1 15.12.2015 19:46
Исправить ошибку Rphoenix C++ Builder 2 28.06.2015 01:38
Как исправить ошибку pakusya Помощь студентам 0 12.05.2013 02:15
как исправить ошибку obsession Общие вопросы Delphi 1 15.04.2012 10:20
Как исправить ошибку Lotles Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 2 22.02.2012 20:11