KACA 2019-無知な食べ物の生放送

4749 ワード

アルゴリズム#アルゴリズム# ココア豆テキストリンク

何回解けますか?

21年10月05日火曜日

ポリシー

私は問題を見て、それから順番に漸進してみましたが、考えてみると、k値が長いので、別の方法を考えなければなりません.
またfood timesの要素は10億個あるので、lognで表すことができるstlを使うべきです.

時間の小さい番号を除外した後、残りの番号間の順序を把握することで行うことができます.
->広範囲に押し出すと問題が近づきやすいからです.

だから先に時間の大きいやつを取り除くなら、kの条件を処理して、大きいやつ*のサイズを取り除く必要があります.
子供の空き地をどうするかと思うと、まず子供を引き出したいと思っています.
=>結論:優先順位キュー-降順で並べ替え、上部から削除します.

本当に大切なのは

の合計所要時間を測定する変数があるはずです.

優先キューはすべてのコンテナで参照できないため、
測定する変数が必要です.この変数で後の値を比較できます.

そっと

非参照解のコード

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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

bool compare2(pair<int,int>a, pair<int,int>b)
{
    return a.first < b.first;
}

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    
    long long sum = 0;
    for(const auto i : food_times)
        sum += i;
    
    if(sum <= k)
        return -1;
    
    //인덱스 번호 - 소요 시간
    priority_queue<pair<int,int>,vector<pair<int,int>>, compare>pq;
    
    for(int i = 0; i < food_times.size(); i++)
    {
        pq.push({i + 1, food_times[i]});
    }
    
    long long totalTime = 0;
    long long totalCnt = 0;
         
    while( (k - totalTime ) >= pq.size() * ( pq.top().second - totalCnt )  ) 
    {
        int cnt = pq.top().second - totalCnt;
        //이후의 남겨진 pq의 소요시간을 줄이기 위한 변수...
        totalCnt += cnt;         
        //제거 될때마다 cnt값은 달라진다. 
        totalTime += pq.size() * cnt;      
        pq.pop();        
    }
   
    //나열시키자.
    vector<pair<int,int>>v;
    
    while(!pq.empty())
    {
        v.push_back({pq.top().first, pq.top().second});       
        pq.pop();
    }
    
    //일단 오름차순으로 정렬하자.
    sort(v.begin(), v.end(), compare2);
    
    long long spareTime = k - totalTime;
    long long index = (spareTime) % v.size();
    answer = v[index].first;
    
    return answer;
}