[白俊]1461-グリディ(図書館)

6584 ワード
アルゴリズム#アルゴリズム# テキストリンク

問題を解く


質問https://www.acmicpc.net/problem/1461
  • 受信input
    複数の入力を把握してリストを作成する方式
    • n, m = map(int, input().split())
points = list(map(int, input().split()))
  • 最小距離を求めるため、正数座標と負数座標に分けて
    • plus=[]
minus=[]

for i in points:
	if i>0:
    	plus.append(i)
    else:
    	minus.append(i)
  • 両手を降順に逆、負数をabsで降順に作る
  • 節価が高いから移動
    • plus.sort(reverse=True)
minus.sort()
  • 最も遠い座標は戻さずに最後に移動しなければならない
    • max_distance=0
for i in points:
	if abs(i)>abs(max_distance):
    	max_distance=i
    max distanceを0に設定し、リストのベンド値が0より大きい場合は更新します.
  • 節価最大の数字から、リストからmを移動し、距離に追加
  • 例m=2、plus=[5,4,3,2,1]は(5.4)(3,2),(1)->5,3,1が追加された
    • distance=[]

for i in range(0, len(plus), m):
	if plus[i] != max_distance:
    	distance.append(plus[i])
        
for i in range(0, len(minus), m):
	if minus[i] != max_distance:
    	distance.append(minus[i])
  • 総移動距離をmaxディスタンスに設定し、距離に往復距離を1つ追加
    • result = abs(max_distance)

for i in distance:
	result += abs(i*2)

print(result)

    の最後の部分


    これまで解いたアルゴリズム問題の中で,最も複雑である.(初心者の話題ㅠㅠ)
    コードを書きながらabs()を繰り返したくないので、最初から負の値を作っていたときからabsと書いていたら、間違った答えが出てしまいました.
    私のコードが間違っているのか、何が正しいのかを確認して更新します.
    Scope
    thinkphp5.0アシスタント関数大全