[プログラマー]無知な食べ物の生放送

質問する
無知な食いしん坊生活

효율성 테스트에 부분 점수가 있는 문제입니다.

普段食欲旺盛な武智は才能を見せようと苦悩の末、カカオテレビで生放送することにする.
食いしん坊放送だけをするのは他の放送と変わらないので、武智は次のようなユニークな方法を考え出した.
ターンテーブルにはN品の料理があります. それぞれの食べ物には1からNまで番号があり、それぞれの食べ物を摂取するのに一定の時間がかかります. 無知は以下の方法で食べ物を摂取する.

無知は1番の食べ物から食べ始め、ターンテーブルは番号が増えた順に食べ物を無知の前に持っていく.

の最後の番号の食べ物を摂取した後、回転盤によると、最初の食べ物は再び無知の前に来た.

無知は1つの食べ物を1秒摂取した後、残りの食べ物をそのままにして、次の食べ物を摂取する.

次の食べ物とは、残りの食べ物の中で最も番号に近い食べ物を摂取することです.

ターンテーブルが次の料理を前に持っていくのにかかる時間がないと仮定します.

無知が放送K秒を食べ始めた後、ネットの故障で放送が一時中断した.インターネットが正常化して再放送された時、何回か食べ物から摂取すべきか知りたい. 解題関数を完成させ,すべての食物を含む所要時間をfood回配列し,ネットワーク障害が発生した時間K秒をパラメータとして与えた場合,数回の食物から再摂取すれば戻ることができる.
せいげんじょうけん

food timesは、すべての食べ物を食べるのに要する時間を食べ物の番号順に並べた食べ物です.

kは、放送が中断された時間を示す.

再摂取が必要な食べ物がなければ  1を返却すればいいです.

精度テストの制限

food倍の長さは  1  以上  2,000  より低い

food倍の元素は  1  以上  1,000  以下は自然数です.

k  1  以上  2,000,000  以下は自然数です.

効率テストの制限

food倍の長さは  1  以上  200,000  より低い

food倍の元素は  1  以上  100,000,000  以下は自然数です.

k  1  以上  2 x 10^13  以下は自然数です.

I/O例
Untitled
I/O例説明
I/O例#1

0-1秒以内に、1番の食べ物を摂取します.残りの時間は[2,1,2]です.

1~2秒以内に2回食事をとる.残りの時間は[2,0,2]です.

2~3秒以内に3回食事をとる.残りの時間は[2,0,1]です.

~4秒以内に、1番の食べ物を摂取します.残りの時間は[1,0,1]です.

4~5秒以内(2番の食べ物が食べ終わった)に、3番の食べ物を摂取します.残りの時間は[1,0,0]です.

5秒でネットワーク障害が発生.1番の食べ物は摂取が必要な時に中断したので、故障が回復した後、1番の食べ物から食べればいいです.

アイデア
初めての試み
限られた時間内に、繰り返し検査することで摂取時間を減らす.このとき、その時間になると、結果が出力されます.
ソースコード

food_times = [2,1,3]
k = 4

def solution(food_times, k):
    time = 0
    while True:
        for i in range(len(food_times)):
            if time == k:
                if sum(food_times) == 0:
                    answer = -1
                else:
                    answer = i + 1
                return answer
            if food_times[i] != 0:
                food_times[i] = food_times[i] - 1
                time += 1

print(solution(food_times,k))

→コミット結果:一部のみ成功
2回目の試み
反例発見
food times=[1100]k=10の場合、結果は2であるべきであるが、1番目のコードは1であるため、条件が追加される.
ソースコード

food_times = [1,100]
k = 10

def solution(food_times, k):
    time = 0
    while True:
        for i in range(len(food_times)):
            if time == k:
                if sum(food_times) == 0:
                    answer = -1
                if food_times[i] == 0:
                    continue
                else:
                    answer = i + 1
                return answer
            if food_times[i] != 0:
                food_times[i] = food_times[i] - 1
                time += 1

print(solution(food_times,k))

→結果の提出:4つのテストケースタイムアウト
いずれにしても時間複雑度はO(N^2)なのでタイムアウトが発生した可能性があります.
他の計算式や関数を使う必要があるようです.この問題も勉強するときに他の人の解答を参考にして修正する必要があります.