Решение задачи Построение массива с Codeforces

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

Вам задана массив a длины n, состоящий из нулей. Вы выполняете n действий с этим массивом: в течение i-го действия происходит следующая последовательность операций:

Выбирается максимальный по длине подмассив (последовательный подотрезок), состоящий только из нулей, среди всех таких отрезков выбирается самый левый;
Пусть этот отрезок равен [l;r]. Если r−l+1 нечетно (не делится на 2), то присваивается a[l+r2]:=i (где i — номер текущего действия), иначе (если r−l+1 четно) присваивается a[l+r−12]:=i.
Рассмотрим массив a длины 5 (изачально a=[0,0,0,0,0]). Тогда он меняется следующим образом:

Сначала мы выбираем отрезок [1;5] и присваиваем a[3]:=1, таким образом a становится равен [0,0,1,0,0];
затем мы выбираем отрезок [1;2] и присваиваем a[1]:=2, таким образом a становится равен [2,0,1,0,0];
затем мы выбираем отрезок [4;5] и присваиваем a[4]:=3, таким образом a становится равен [2,0,1,3,0];
затем мы выбираем отрезок [2;2] и присваиваем a[2]:=4, таким образом a становится равен [2,4,1,3,0];
и наконец мы выбираем отрезок [5;5] и присваиваем a[5]:=5, таким образом a становится равен [2,4,1,3,5].
Ваша задача — найти массив a длины n после выполнения всех n действий. Заметьте, что ответ существует и единственен.

Вам необходимо ответить на t независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		set<pair<int, int>, cmp> segs;
		segs.insert({0, n - 1});
		vector<int> a(n);
		for (int i = 1; i <= n; ++i) {
			pair<int, int> cur = *segs.begin();
			segs.erase(segs.begin());
			int id = (cur.first + cur.second) / 2;
			a[id] = i;
			if (cur.first < id) segs.insert({cur.first, id - 1});
			if (id < cur.second) segs.insert({id + 1, cur.second});
		}
		for (auto it : a) cout << it << " ";
		cout << endl;
	}
	
	return 0;
}

         

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


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

Это просто задача на реализацию. Мы можем использовать какой-нибудь вид кучи или же упорядоченного множества, чтобы сохранить все отрезки, которые нам нужны, в нужном нам порядке. Чтобы решить эту задачу на C++ с использованием std::set, мы можем просто переписать компаратор для std::set таким образом:

struct cmp {
bool operator() (const pair &a, const pair &b) const {
int lena = a.second - a.first + 1;
int lenb = b.second - b.first + 1;
if (lena == lenb) return a.first < b.first;
return lena > lenb;
}
};
А затем просто написать std::set следующим образом:

set, cmp> segs;
Теперь минимальный элемент этого множества будет означать отрезок, который нам необходимо выбрать. Изначально множество будет содержать только один отрезок [0;n−1]. Допустим, мы выбираем отрезок [l;r] в течение i-го действия. Пусть id=⌊l+r2⌋, где ⌊xy⌋ равно x деленному на y с округлением вниз. Присвоим a[id]:=i, затем, если отрезок [l;id−1] имеет положительную (большую нуля) длину, добавим этот отрезок в множество, и то же самое сделаем с отрезком [id+1;r]. После n таких действий мы получим ответ.

Асимптотика решения: O(nlogn).


Комментарии

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



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

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

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