模擬地区予選2010 I. Operator

I. Operator

なんか講評よりオーダーが良かったので晒してみます。
嘘の告発は(ry
一応、二分探索＋ちょっとではありません。

解法

• 基本はJAGの講評に準拠
• オペレータの数が小さい方からシミュレーション
• オペレータは区別しなくて良いので各時間でヒマな人数だけ覚えておく
  • 各時間ではヒマな人数分だけ電話を処理できる
  • 電話を処理したら処理後の時間に1人追加
  • ヒマな人が余ったら次の時間に持ち越し
• 全体でO(TN^2)

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

bool simulate(const vector<int> &L, const vector< pair<int, int> > &vp, int T, int M){
    int N = vp.size();
    vector<int> lest(T+1, 0);
    vector<bool> ok(vp.size(), false);
    for(int i=0;i<M;i++) lest[L[i]]++;
    int cnt = N-M;
    for(int i=1;i<T;i++){
        if(cnt == 0) return true;
        if(lest[i]==0) continue;
        for(int j=M;j<N;j++){
            if(ok[j]) continue;
            if(i%vp[j].second <= vp[j].first){
                if(i+L[j] > T) return false;
                cnt--;
                ok[j] = true;
                lest[i]--;
                lest[i+L[j]]++; 
            }
            if(lest[i] == 0) break;
        }
        lest[i+1] += lest[i];
    }
    return cnt == 0;
}

int main(){
    int N, T;
    ifstream fin("I.txt");
    while(fin >> N >> T, N){
        vector<int> L(N);
        vector< pair<int, int> > vp(N);
        for(int i=0;i<N;i++){
            fin >> L[i] >> vp[i].first >> vp[i].second;
            vp[i].second += vp[i].first;
        }
        for(int i=1;i<=N;i++){
            if(simulate(L, vp, T, i)){
                cout << i << endl; break;
            }
        }
    }
}