[BOJ]1700マルチタブスケジューリング
2152 ワード
バックグラウンド1700マルチタブスケジューリング(Python)[G 1]
グレースケールアルゴリズム
一瞬ごとに最高の選択をします.
この問題では,新しい電子機器を挿入する際に,既存の電子機器を取り除くことが最も重要である.
思想回路.セット複数のラベル. 初期の場合、マルチタブは空で、順番に挿入します. 最初から重複している可能性があるしたがって,Kより小さいまで集合の大きさをNとする. (重複データ削除から重複文を行う)huboリスト:index iから最後に入力した要素まで、選択される候補者. プレースホルダ不要(複数のタブを挿入):continue マルチタブ要素の中で候補外の場合:削除する. それでも位置がない->候補者を後ろから見て複数のタグの中の要素を複数のタグから外す. 発生位置->挿入->count++ 注意事項i+1は1つ目の要素を候補に入れ、重要なのは最初から加え、重複をなくすこと.
[3, 1, 1, 2, 3, 3] is [3, 1, 2] not [1, 2, 3] python setデータ構造はインデックスできません->リストにコピーして解決 新挿しが標準で最後に空席があっても大丈夫
グレースケールアルゴリズム
一瞬ごとに最高の選択をします.
この問題では,新しい電子機器を挿入する際に,既存の電子機器を取り除くことが最も重要である.
思想回路.
[3, 1, 1, 2, 3, 3] is [3, 1, 2] not [1, 2, 3]
import sys
if __name__ == '__main__':
N, K = map(int,sys.stdin.readline().split(' '))
linput = list(map(int,sys.stdin.readline().split(' ')))
count = 0
mt = set()
tmp = 0
while len(mt) < N and len(linput) > tmp:
mt.add(linput[tmp])
tmp = tmp + 1
# 처음은 멀티탭이 비어있으니, 일단 꽂음.
# 중복된 건 꽂을 필요 없으니 중복 제거하여 꽂음
for i in range(tmp,len(linput)):
hubo1 = linput[i+1:]
# 다음에 꽂을 전자기기 중복 제거, 순서 유지
hubo = []
[hubo.append(v) for v in hubo1 if v not in hubo]
mtl = list(mt)
#집합 인덱싱을 위해 리스트로 변환
if linput[i] in mt:
if linput[i] not in hubo:
mt.remove(linput[i])
mtl.remove(linput[i])
#이미 있는 건데 이제 안 써? 뽑아
continue
#이미 있으면 그냥 지나감
for j in range(len(mtl)):
if mtl[j] not in hubo:
mt.remove(mtl[j])
mtl.remove(mtl[j])
break
#이제 꽂을 일 없는 전자기기는 빼버림
hubo.reverse()
if len(mt) == N: # 그래도 자리가 없으면
for j in range(len(hubo)):
if hubo[j] in mt:
mt.remove(hubo[j])
break
#맨 뒤에서부터 사용할 전자기기를 뺌
if len(mt) < N:
if linput[i] not in mt:
mt.add(linput[i])
count = count + 1
else:
print("Error")
exit()
print(count)
Reference
この問題について([BOJ]1700マルチタブスケジューリング), 我々は、より多くの情報をここで見つけました https://velog.io/@csk/BOJ-1700-멀티탭-스케줄링-lt8wt694テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol