アルゴリズムマラソン4日目
22210 ワード
21日
木を切る
これは典型的なバイナリ検索問題です.タイムアウト...😭
タイムアウトコード
N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree)
while start <= end:
mid = (start + end) // 2
total = 0
for i in tree:
if i >= mid:
total += i - mid
if total >= M:
start = mid + 1
else:
end = mid - 1
print(end)N, M = map(int, input().split())
tree = list(map(int, input().split()))
def sum_tree(height):
sum = 0
for i in tree:
if i - height > 0:
sum += (i - height)
return sum
def binarySearch(target):
start, end = 0, max(tree)
ans = 0
while start <= end:
mid = (start + end) // 2
sum = sum_tree(mid)
if sum < target:
end = mid - 1
if sum >= target:
ans = mid
start = mid + 1
return ans
print(binarySearch(M))22日
スタック
Sysはinput()関数より大きい.stdin.readline()は速度が速い.時間短縮が可能になります.
import sys
cmd_cnt = int(sys.stdin.readline())
stack = []
for i in range(cmd_cnt):
cmd = sys.stdin.readline().split()
if cmd[0] == 'push':
stack.append(int(cmd[1]))
elif cmd[0] == 'pop':
if not stack:
print(-1)
else:
print(stack.pop())
elif cmd[0] == 'size':
print(len(stack))
elif cmd[0] == 'empty':
if not stack:
print(1)
else:
print(0)
elif cmd[0] == 'top':
if not stack:
print(-1)
else:
print(stack[-1])23日です。
ゼロ。
やさしい
cnt = int(input())
stack = []
for i in range(cnt):
num = int(input())
if num == 0:
stack.pop()
else:
stack.append(num)
print(sum(stack))24日
かっこ
やっぱり簡単ただし、閉じた括弧が開いた括弧よりも多くなると、後にどんなことがあっても括弧は完成しないのでNOと判断する.
case_cnt = int(input())
for i in range(case_cnt):
case = input()
case_list = list(case)
sum = 0
for i in case_list:
if i == '(':
sum += 1
elif i == ')':
sum -= 1
if sum < 0:
print('NO')
break
if sum > 0:
print('NO')
elif sum == 0:
print('YES')25日
最小公倍数
アルゴリズムマラソン3日目の16番の問題を復習したら、必ず正解しなければならない.
ユークリッド湖の作り方を知っていれば、簡単になります.
2つの数の最大公約数は、2つの数の小数と、2つの数の大きな数を小数で割った最大公約数に等しい.
gcd(24,18)=gcd(18,6)=gcd(6,0)のうち、小数が0の瞬間の大数が最大公約数である.
最大公約数を求めると、最小公倍数は、2つの数に最大公倍数を乗じることに等しい.
def gcd(x, y):
mod = x % y
while mod > 0:
x = y
y = mod
mod = x % y
return y
def lcm(x, y):
return x * y // gcd(x, y)
cnt = int(input())
for i in range(cnt):
a, b = map(int, input().split())
print(lcm(a, b))26日です。
二項係数1
ソートと組合せの概念を理解するには.逐次配列(Permutation)、逐次配列(Combination)
したがって、シーケンスは
n!/n-r!であり、組合せはn!/r!(n-r)!であるfrom math import factorial
n, k = map(int, input().split())
b = factorial(n) // (factorial(k) * factorial(n - k))
print(b)Reference
この問題について(アルゴリズムマラソン4日目), 我々は、より多くの情報をここで見つけました https://velog.io/@seanstainability/알고리즘-마라톤-4일차テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol