Решение задачи Максимальный квадрат с Codeforces

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

Уджан решил сделать новую крышу для своего дома. У него есть n прямоугольных досок, пронумерованных числами 1 до n. У i-й доски размеры ai×1 (то есть ширина равна 1, а высота равна ai).

В данный момент Уджан хочет сделать квадратную крышу. Сначала он выберет некоторые доски и расположит их одну за другой в каком-то порядке. Затем он склеит все эти доски по их вертикальным сторонам. Наконец, он вырежет квадрат из получившейся фигуры таким образом, что стороны квадрата горизонтальны и вертикальны.

Например, если у Уджана есть доски с длинами 4, 3, 1, 4 и 5, он может выбрать доски с длинами 4, 3 и 5. Тогда он может вырезать квадрат размером 3×3, который является наибольшим возможным. Учтите, что в данном случае это не единственный способ получить квадрат размером 3×3.
Чему равняется наибольшая длина стороны квадрата, который может получить Уджан?

Код 

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<int> a(n);
		for(int i = 0; i < n; i++)
            cin >> a[i];
		sort(a.begin(), a.end());
		int i = 0;
		while(n - i > a[i]){
			i++;
		}
		cout << n - i << endl;
	}
	return 0;
}

         

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


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

У этой задачи есть различные решения:

Решение 1: Переберём длину стороны квадрата l от 1 до n. Если возможно сделать квадрат со стороной l, тогда должно быть по крайней мере l досок длиной по крайней мере l. Время работы такого решения: O(n * n). Параметр l также можно найти и двоичным поиском: тогда время работы становится O(nlogn).

Решение 2: Допустим, что мы хотим выбрать i досок и вырезать наибольший квадрат из них. Естественно, всегда выгоднее выбрать i самых длинных досок. Сторона наибольшего квадрата, который можно вырезать из них, ограничена длиной самой короткой из этих i досок и количеством досок, i. Поэтому решение такое: упорядочить числа a[i] в убывающем порядке; тогда ответом является max(min(i,a[i])). Время работы: O(nlogn). Так как числа a[i] не превышают n, мы можем использовать сортировку подсчётом и тогда время работы становится O(n).


Комментарии

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



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

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

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