問題を理解する💬

白駿#11399 ATM
ATMの前にN人が並んでいました.人は1番からN番まで、i番の引き出しにかかる時間はPi分です.
一人当たりの引き出しにかかる時間の合意最高値を求める.
並んでいる順番が時間全体と変わります.
時間を求める方法
P 1=3、P 2=1、P 3=4、P 4=3、P 5=2の場合
順番に引くと3+4+8+11+13=39点
[P 2=1,P 5=2,P 1=3,P 4=3,P 3=4]順番に並び、1+3+6+9+13=32分

初志😀

最小時間の合計
=前の順序であればあるほど小数点以下が多くなり、
次の順番(繰り返し回数が一番少ないため)ほど、大きな数字が繰り返し回数が一番少ないのに加えて、これが一番少ないのではないでしょうか.
それは昇順に並べて、加えて、それは最高値ではありませんか?
こんな簡単なことあるのか…?保証できますか.
自惚れすぎて、保証するより複雑さを考えたほうがいい.
複雑さ
最も時間がかかるのはソートO(Nlogn)であるため,複雑度G c

数式化

フィボナッチでそれぞれPiを救うのは効率が悪いように見えます.

Pi*(アレイ長-i)を次のように求めます.
フィボナッチですべての要素を求めるよりも、それらを全部合わせて答えを求めるよりも少ない計算で求めることができると思います.
フィボナッチ数列の時間複雑度はO(2^N)である,
上記の式で求めた複雑さは[O(N)]であり,できればより良い加算であるはずである.

コード1👩🏻‍💻

# 모든 사람들의 출금 전체 시간을 계산한다
def calc(arr, n) :
  res = 0
  for i in range(n) : res += arr[i] * (n-i)
  return res

n = int(input())
A = list(map(int,input().split()))
A.sort() # 오름차순으로 정렬
print(calc(A, n))

渡航!