計画-先入先出のスケジュール

2306 ワード
プログラマ アルゴリズム#アルゴリズム# テキストリンク
計画-先入先出のスケジュール
二分探索で解決できる.
まず、この方への探索を通じて、終わりの時間を求めます.(finish_time)
この探索を行う過程で、今の角度から、核心たちが何をしたのかを見つけて、彼らの和を求めます.
この和がn未満の場合、leftはmidに更新され、逆にrightはmidに更新される.
この探索が完了すると、finish timeから1を減算した時間内にコアの合計ワークセットが求められ、nから減算される.
次にfinish timeでは、動作を開始するカーネルがあるたびにnから1を減算し、0の場合は対応するカーネルインデックスを返します.
実はこの問題は85点か90点くらいでずっと間違っていて少し迷っていて、2点探索問題を解くと同時にwhile-loopが終わる条件と2点探索の左、右更新に違いがあります.
私は以前while(left<=right)の形式でwhile-loop条件を設定して、left=mid+1;right = mid - 1;更新してくれた
問題は,このようにして特定のmid値を省略した結果,左から右の間のすべての二分探索が可能なmid値に対して二分探索は行われていないようである.
前の条件はwhile(left+1コードは以下の通りです.
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> cores) {
    int answer = 0;
    int left = 0;
    int right = 1 << 20;
    
    while(left + 1 < right) {
        int mid = (left + right) / 2;
        
        int current = cores.size();
        for(int i=0;i<cores.size();i++) 
            current += (int)(mid / cores[i]);
        
        if(current < n) 
            left = mid;
        else 
            right = mid;
    }
    n -= cores.size();
    if(n <= 0) 
        return n;
    
    for(int i=0;i<cores.size();i++) 
        n -= (int)((right - 1) / cores[i]);
    
    for(int i=0;i<cores.size();i++) {
        if((right % cores[i]) == 0) 
            n--;
        if(n == 0)
            return i + 1; 
    }
    return answer;
}
HackerRank : Staircase
LintCode 439 [Segment Tree Build II]