もっと辛い

問題の説明

辛いのが好きなLeoは全ての食べ物のScobile指数をK以上にしたいすべての食べ物のScobile指数がK以上になるように、LeoはScobile指数が最も低い2つの食べ物を以下のような特殊な方法で混合し、新しい食べ物を作った.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leoは、すべての食べ物のスコビル指数がK以上になるまでかき混ぜます.
Leoが持つ食べ物のスコヴェル指数とScoville指数がKに達したとき、すべての食べ物のスコヴェル指数をK以上に混合する最小回数を返す解関数を作成してください.

せいげんじょうけん

scovilleの長さは2以上100000以下である.

Kは0以下です.

scovilleの各要素は0または1000000未満です.

すべての食品のスコヴェル指数がKを超えない場合、−1を返す.

ソースコード

C++

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i=0;i<scoville.size();i++) {
        pq.push(scoville[i]);
    }
    
    while(pq.top()<K) {
        // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
        if(pq.size()==1) {
            answer=-1;
            break;
        }
        
        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();
        pq.push(x+2*y);
        answer++;
    }
    
    return answer;
}

java

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int s : scoville) {
            pq.add(s);
        }
        // 가장 맵지 않은 음식의 스코빌 지수가 K보다 작으면 반복
        while(K > pq.peek()) {
            // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
            if(pq.size() < 2) {
                return -1;
            }
            int food1 = pq.poll();
            int food2 = pq.poll();
            pq.add(food1 + food2*2); // 섞기
            answer++;
        }
        return answer;
    }
}

感想

HIP->優先キュー😎