無知な食いしん坊生活

*効率テストでは、得点の一部が得られます.
普段食欲旺盛な武智は才能を見せようと苦悩の末、カカオテレビで生放送することにする.

食いしん坊放送だけをするのは他の放送と変わらないので、武智は次のようなユニークな方法を考え出した.
ターンテーブルには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以下の自然水である.

初志

food_timesアレイ周辺
0より大きい場合はsecondおよびindex+1、food_times-1
0の場合はindex+1
繰り返して、secondがkになるまで、すればいいのではないでしょうか.

初回試行(失敗)

def solution(food_times, k):
    answer = -1
    index=0
    second=0
    
    while second<=k:
        index=index%len(food_times)
        if len(food_times)==food_times.count(0):
            answer=-1
            return answer
        if food_times[index]>0:
            food_times[index]-=1
            index+=1
            second+=1
        else:
            index+=1
        
    
    print(food_times)
    answer=index
    return answer

採点結果
精度:42.9
効率:0.0
合計:42.9/100.0
正確性だけが正しい、効率は全滅...
ハハハハハハ
また保存時に時間が0なら消してしまうと時間が短くなるのでしょうか?
やってみたいのですが、これも失敗しました...やれやれ
最終的にこの問題はいくつかの計算を利用して解決する必要があります.ここで重要なのは、k秒以内にできるだけ多くの食べ物を食べ(食事を通じて)、秒数を増やすために必要な計算回数を減らすことです.
だから一番少ない食べ物(ろうそくが一番少ない)から順番に出します.heapqを使わなければなりません!

二次試行(成功)

import heapq
def solution(food_times, k):
    
    #전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times)<=k:
        return -1
    
    q=[]
    for i in range(len(food_times)):
        #(음식 시간, 음식 번호) 형태로 heapq에 삽입
        heapq.heappush(q, (food_times[i], i+1))
    
    sum_value = 0 #먹기 위해 사용한 시간
    previous = 0 #직전에 다 먹은 음식 시간
    
    length = len(food_times) #남은 음식의 개수
    
    #sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 남은 음식 개수와 k 비교
    #위가 현재 전체 남은 시간(k)보다 커질때까지 반복한다
    while sum_value+((q[0][0]-previous)*length)<=k:
        now=heapq.heappop(q)[0] #현재의 음식 시간
        sum_value += (now-previous)*length 
        length -= 1 #다 먹은 음식 제외
        previous = now #이전 음식 시간 재설정
    
    #남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x:x[1]) #음식의 번호 기준으로 정렬
    return result[(k-sum_value)%length][1] #번호 기준으로, 남은 초수(k-sum_value) 만큼 반복
    answer = -1
    return answer