Problem - 1197A - Codeforces
codeforces.com
K+2개 중 첫번째로 긴 널빤지와 두번째로 긴 널빤지를 '세로'로 둔다
'세로'에서 두번째로 긴 널빤지의 길이와 나머지 널빤지 갯수 K개를 비교하여 결정한다
- 제목
DIY Wooden Ladder
- 조건
time limit per test : 2 seconds
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
Let's denote a K-step ladder as the following structure: exactly K+2 wooden planks, of which
- two planks of length at least K+1 — the base of the ladder;
- K planks of length at least 1 — the steps of the ladder;
Note that neither the base planks, nor the steps planks are required to be equal.
For example, ladders 1 and 3 are correct 2-step ladders and ladder 2 is a correct 1-step ladder. On the first picture the lengths of planks are [3,3][3,3] for the base and [1][1] for the step. On the second picture lengths are [3,3][3,3]for the base and [2][2] for the step. On the third picture lengths are [3,4][3,4] for the base and [2,3][2,3] for the steps.
You have N planks. The length of the i-th planks is ai. You don't have a saw, so you can't cut the planks you have. Though you have a hammer and nails, so you can assemble the improvised "ladder" from the planks.
The question is: what is the maximum number K such that you can choose some subset of the given planks and assemble a K-step ladder using them?
- 입력
The first line contains a single integer T (1≤T≤100) — the number of queries. The queries are independent.
Each query consists of two lines. The first line contains a single integer nn (2≤n≤10^5) — the number of planks you have.
The second line contains nn integers a1,a2,…,an (1≤ai≤10^5) — the lengths of the corresponding planks.
It's guaranteed that the total number of planks from all queries doesn't exceed 10^5.
- 출력
Print T integers — one per query. The i-th integer is the maximum number K, such that you can choose some subset of the planks given in the i-th query and assemble a K-step ladder using them.
Print 0 if you can't make even 1-step ladder from the given set of planks.
| 예제 입력 1 | 4 4 1 3 1 3 3 3 3 2 5 2 3 3 4 2 3 1 1 2 |
| 예제 출력 1 | 2 1 2 0 |
- 힌트
Examples for the queries 1~3 are shown at the image in the legend section.
The Russian meme to express the quality of the ladders:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int test_case, size, standard;
int* arr;
cin >> test_case;
for (int n = 0; n < test_case; n++) {
cin >> size;
arr = new int[size];
for (int m = 0; m < size; m++)
cin >> arr[m];
sort(arr, arr + size);
standard = arr[size - 2];
if (size - 2 >= standard)
cout << standard - 1 << endl;
else
cout << size - 2 << endl;
}
return 0;
}