TIL 37|ATMグリッドアルゴリズム+DP(標準11399 python)

問題のショートカット

問題の概要

角. 人ですね. お金を. お金を引き出す時. 必要 時間の の意見を打診 最高値

条件

1. 角. だれもが お金を引き出す時. 掛ける. 時間. 違います.
2. ATMギガ 漢韓対訳辞典 大学だから. 前面 人々. すべて 処理する前に. 待たなければなりません. 始まりました.
3. いいですよ. 徐. 順次 ついて行く 必要 時間の 二つを一つにする 変わります.

方法

1. 処理時間 少ないです. 掛ける. 人から始まる 処理すると. ますます せきさん 待ち時間 げんすい 数 あります.
2. 無条件 小さい 値段から 処理しても. 最適 太陽 区轄 数 あります.
3. すなわち グリディ アルゴリズム#アルゴリズム# 使用しても 1リットル に質問 相当.
4.時間の和を求める.従来の値を用いて蓄積することから,dp方式が出現した.dp方式と非dp方式.

コードせっけい

1. 人. 数を数える. 入力 次です. 行は次のとおりです. 角. 人の 金を引き出す 処理時間 pを 漢韓対訳辞典 1回 入力 リスト内 貯蔵する.
2. 昇順 を選択します.
3. リスト 前面 位置 要素 はじめから お得 時間. 積み重ねる.
3-1. 論理全体は、DP方式のバージョンではなく、同じ時間の和を求める方式をDP方式のバージョンに変えた.

DP合計コード

初めて>間違えた!

import sys
r=sys.stdin.readline
n = int(r())
p_list = sorted(list(map(int, r().split())))
dp = []
for p in p_list:
    if p_list.index(p) == 0: -------- 🐞
        dp.append(p)
    else:
        dp.append(dp[-1]+p)
print(sum(dp))

エラーの原因:🐞 index(p)はリスト内の最初のpの位置のみを返すため、最初の数字と同じ値が存在する場合、累積演算を行わずにpをdpに追加する.

修正後の正しいコード

import sys
r=sys.stdin.readline
n = int(r())
p_list = sorted(list(map(int, r().split())))
dp = [p_list[0]]
for p in p_list[1:]:
        dp.append(dp[-1]+p)
print(sum(dp))

変数を使用して結合されたコード

import sys
r=sys.stdin.readline

n = int(r())
p_list = sorted(list(map(int, r().split())))
sum = 0
rst = 0
for p in p_list:
    sum+=p
    rst+=sum
print(rst)

比較結果

前の行はdp方式で採点した結果で、次の行は通常変数を用いて値を積算した結果です.
計算のためにリスト資料を取得し、appendプロセスを経てdp方式は微細であるが、より短い時間がかかると予想される.プログラムが実行されるたびに、サーバコンピュータの状態によって誤差が生じる可能性があります.この程度の違いは比較に意味がありません.