126.無知な食べ物の生放送

プログラマ

普段食欲旺盛な武智は才能を見せようと苦悩の末、カカオテレビで生放送することにする.

食いしん坊放送だけをするのは他の放送と変わらないので、武智は次のようなユニークな方法を考え出した.

ターンテーブルにはNの料理があります.

各食べ物には1からNの番号があり、各食べ物の摂取には一定の時間がかかります.

無知は以下の方法で食べ物を摂取する.

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

最後の番号の食べ物を摂取した後、回転盤によって1番の食べ物が再び現れた.

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

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

回転盤が次の料理を前に出す時間がないと仮定します.

無知がK秒を食べ始めた後、ネットの故障で放送が一時中断した.

インターネットが正常化して再放送されたとき、何回か食べ物から摂取し始めたことを知りたい.

それぞれの食べ物には食べるのに必要な時間の配列food_timesが含まれており、ネットワーク障害発生時間K秒をパラメータとしてreturn関数を完成させ、何回かの食べ物から再摂取すればよい.

せいげんじょうけん

solutionは、それぞれの食べ物を食べるのに要する時間を食べ物の番号順に並べたものです.

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

再摂取が必要な食べ物がなければ、kに戻ればよい.

精度テストの制限

-1の長さは1以上2000以下である.

food_timesの元素は1以上1000以下の自然数である.

food_timesは、1以上200000,000以下の自然水です.

効率テストの制限

kの長さは1以上200000以下です.

food_timesの元素は1以上10000000以下の自然数である.

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

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番の食べ物から食べればいいです.

1.階調アルゴリズム

## 테스트 케이스 50%정도 통과


def solution(food_times, k):

    
    plus = 0
    for _ in range(k):
        rotate = plus % (len(food_times))
        #print('plus', plus)
        #print('rotate',rotate)
        if(food_times[rotate] == 0):
            plus += 1
            rotate = plus % (len(food_times))
            #print('change_rotate', rotate)
        food_times[rotate] -= 1
        plus += 1

        #print(food_times)
   
   

    if food_times[(rotate+1)%3] == 0:
        answer = -1
    else:
        answer = ((rotate+1) % 3) + 1
    return answer

#print(solution([3,1,2], 5))

正解

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.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 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という食べ物が3種類あります.

1番の食べ物:8秒かかります

2番の食べ物:6秒かかります

3番の食べ物:4秒かかります

1)初期段階では,すべての食物を優先順位列(最小臀部)に挿入した.

最後にK = 15秒後に食べる食べ物の番号を印刷する必要があるので、優先キューに挿入するときはKの調音形式で挿入します.

総残存時間(K):15秒

残りの食べ物:3個

2)第1段階において、最も必要とされる食品(음식 시간, 음식 번호)号を除去する.

しかし、まだ3つの食べ物が残っているので、3を外します.
つまり、食べ終わるのに12秒かかります.

残りの時間は15秒から3秒に減少します.

総残存時間(K):15秒

残りの食べ物:2個

食べた食べ物:(4,3)

3)この段階で2番の食べ物を抜く.

食べ物が2つ残っているので、3(남은 음식의 개수) x 4(3번 음식을 먹는 시간) = 12秒です.

今残っている時間は3秒で、これは4より小さいので、外さないでください.

「次の食べる食べ物番号」を探してプリントアウトすればいいです.

全部の残り時間は3秒で、4番目の料理の番号が印刷されたら正解です.

2.C++コード

#include <bits/stdc++.h>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int solution(vector<int> food_times, long long k) {
    // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    long long summary = 0;
    for (int i = 0; i < food_times.size(); i++) {
        summary += food_times[i];
    }
    if (summary <= k) return -1;
    
    // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    priority_queue<pair<int, int> > pq;
    for (int i = 0; i < food_times.size(); i++) {
        // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        pq.push({-food_times[i], i + 1});
    }
    
    summary = 0; // 먹기 위해 사용한 시간
    long long previous = 0; // 직전에 다 먹은 음식 시간
    long long length = food_times.size(); // 남은 음식의 개수

    // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while (summary + ((-pq.top().first - previous) * length) <= k) {
        int now = -pq.top().first;
        pq.pop();
        summary += (now - previous) * length;
        length -= 1; // 다 먹은 음식 제외
        previous = now; // 이전 음식 시간 재설정
    }

    // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    vector<pair<int, int> > result;
    while (!pq.empty()) {
        int food_time = -pq.top().first;
        int num = pq.top().second;
        pq.pop();
        result.push_back({food_time, num});
    }
    sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
    return result[(k - summary) % length].second;
}

3.Javaコード

import java.util.*;

class Food implements Comparable<Food> {

    private int time;
    private int index;

    public Food(int time, int index) {
        this.time = time;
        this.index = index;
    }

    public int getTime() {
        return this.time;
    }

    public int getIndex() {
        return this.index;
    }

    // 시간이 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) return -1;

        // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
            pq.offer(new Food(food_times[i], i + 1));
        }

        summary = 0; // 먹기 위해 사용한 시간
        long previous = 0; // 직전에 다 먹은 음식 시간
        long length = food_times.length; // 남은 음식의 개수

        // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
        while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
            int now = pq.poll().getTime();
            summary += (now - previous) * length;
            length -= 1; // 다 먹은 음식 제외
            previous = now; // 이전 음식 시간 재설정
        }

        // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
        ArrayList<Food> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        // 음식의 번호 기준으로 정렬
        Collections.sort(result, new Comparator<Food>() { 
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.getIndex(), b.getIndex());
            }
        });
        return result.get((int) ((k - summary) % length)).getIndex();
    }
}