Educational Codeforces Round 69 Div2 A

内容

• Educational Codeforces Round 69 A "DIY Wodden Ladder"を解きました。
• python3

問題

本文

• K段のはしごを作りたい。
• K段のはしごは、
  • 長さK+1以上の棒２本(はしごのbase)
  • 長さ１以上の棒 k本(はしごのstep)
    で構成される
• baseの2本は違う長さで良いし、stepも長さはバラバラで良い。
• N本の棒が与えられた時に、構成できる最大のはしごの段数を答えよ。

Input

T: 問題の数
（以下の二つがT回入力される)
N: 棒の本数
A: N本の棒の長さのlist

output

構成できる最大のはしごの段数

link

codeforces.com

考えたこと

• 長い2本をbaseにして、残りをstepにすると良さそう。
• baseが長いほど、段数の大きいはしごが作れる(baseの長さ>=k+1)

ポイント

• baseは長い方から２本選ぶ。
• stepに使えるのは、長さが1以上の枝

実装

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
T = int(input())
for _ in range(T):# T回繰り返す
    N = int(input())
    L = list(map(int, input().split()))
    L = list(filter(lambda x: x >= 1, L)) # stepに使えないものは除く
    L = sorted(L)
    base_len = L[-2]-1 #可能な最大step数は、baseの短い方の長さ-1
    ladder_num = len(L)-2 # stepに使えるのは、baseの二本を除いた棒
    # 答えはbaseによる制約と、stepの棒の制約の小さい方。
    print(min(base_len, ladder_num))