记录编号	544323	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]作业调度方案	最终得分	100
用户昵称	Nuk	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2019-10-17 08:35:38	内存使用	13.66 MiB

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int m, n;
vector<int> seq;
struct Step {
    int mid;
    int time;
    int minstarttime;
};

vector<vector<Step> > workout;
struct Span {
    int start;
    int len;
};

int getEarliest(vector<Span> &mspan, int len, int &before, int &after, int minstart) {
    if(mspan.size() == 0) {
        return minstart; // empty machine
    } else {
        for(int i = 0; i < mspan.size(); i ++) {
            if(i == 0) {
                if(mspan[i].start >= len + minstart) { // slot between 0 and mspan[i].start
                    // get the smallest possible start
                    after = i;
                    return minstart; // fill the earliest slot
                }
            } else {
                int prevend = mspan[i-1].start + mspan[i-1].len;
                int mlen = mspan[i].start - prevend;
                if(mlen >= len && minstart+len <= mspan[i].start) {
                    before = i-1;
                    after = i;
                    return max(minstart, prevend);
                }
            }
        }
        // insert at the back
        before = mspan.size() - 1;
        return max(minstart, mspan.back().start + mspan.back().len);
    }
}

int main() {
    ifstream fin("jsp.in");
    // n items, each item m steps
    fin >> m >> n;
    for(int i = 0; i < m*n; i ++) {
	    int t;
	    fin >> t;
	    seq.push_back(t);
    }
    workout = vector<vector<Step> >(n+1, vector<Step>(m+1, Step{}));
    for(int i = 1; i <= n; i ++) {
	    for(int j = 1; j <= m; j ++) {
            int t;
            fin >> t;
            workout[i][j].mid = t;
	    }
    }
    for(int i = 1; i <= n; i ++) {
	    for(int j = 1; j <= m; j ++) {
		    int t;
		    fin >> t;
		    workout[i][j].time = t;
	    }
    }
    
    int total = 0;
    vector<int> currentStep = vector<int>(n+1, 1);
    vector<vector<Span> > mspan = vector<vector<Span> >(m+1, vector<Span>());
    for(int i = 0; i < m * n; i ++) {
        int citem = seq[i];
        int cstep = currentStep[citem];
        Step s = workout[citem][cstep];
        int cmachine = s.mid;
        int citemstart = s.minstarttime;
        int before = -1, after = -1;
        int cstart = getEarliest(mspan[cmachine], s.time, before, after, citemstart);
        
        if(after == -1) { // insert at the end
            mspan[cmachine].push_back(Span{.start = cstart, .len = s.time});
        } else { // insert at position after
            vector<Span>::iterator it = mspan[cmachine].begin();
            mspan[cmachine].insert(it+after, Span{.start = cstart, .len = s.time});
        }
        currentStep[citem] ++;
        if(currentStep[citem] <= m) {
            workout[citem][currentStep[citem]].minstarttime = cstart + s.time;
        }
    }
   
    for(int i = 1; i <= m; i ++) {
        if(!mspan[i].size()) {
            continue;
        }
        Span &s = mspan[i].back();
        if(total < s.start + s.len) {
            total = s.start + s.len;
        }
    }
    
    ofstream fout("jsp.out");
    fout << total << endl;
    
    return 0;
}