Решение задачи "Лестница своими руками" с Codeforces

Без пояснения   Просмотров: 14

Назовем k-ступенчатой лестницей следующую конструкцию: ровно k+2 деревянные доски, среди которых

две доски длиной хотя бы k+1 — основные направляющие лестницы;
k досок длиной хотя бы 1 — ступеньки лестницы.
Заметим, что ни направляющие, ни ступени не обязаны быть равны.

Например, лестницы 1 и 3 — корректные 2-ступенчатые лестницы, а лестница 2 — корректная 1-ступенчатая. На первом изображении длины досок равны [3,3] для направляющих и [1] для ступеньки. На втором изображении длины досок равны [3,3] для направляющих и [2] для ступеньки. На третьем изображении длины досок равны [3,4] для направляющих и [2,3] для ступенек.

У вас есть n досок. Длина i-й доски равна ai. У вас нет пилы и вы не можете распиливать доски. Зато есть молоток и гвозди, и вы можете собрать импровизированную «лестницу» из тех досок, что есть.

Вопрос в следующем: чему равно максимальное k такое, что вы сможете собрать k-ступенчатую лестницу, используя некоторый поднабор из имеющихся досок?

Код 

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200000];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
			cin>>a[i];
		sort(a,a+n);
		cout<<min(n-2,a[n-2]-1)<<endl;
	}
	return 0;
}

         

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


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

Комментарии

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