思想：采用小顶堆，每台机器一有空，就从工作中挑选一个工作时间最长的。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class MechineNode
{
public:MechineNode(int id, int start, int JobId = 0) {this->ID = id;this->start = start;this->JobId = JobId;};MechineNode() {};int ID, start, JobId;};
class JobNode
{
public:JobNode() {};JobNode(int id, int time){this->ID = id;this->time = time;}int ID, time;};
bool cmp1(JobNode& j1, JobNode& j2)
{return j1.time <j2.time;
}
struct cmp
{bool operator()(const MechineNode& m1, const MechineNode& m2){return m1.start >m2.start;}
};
void visit(vector<vector<int>>& v)
{for (int i = 1; i <v.size(); i++){cout << i << ": ";for (int j = 1; j <v[i].size(); j++)cout << v[i][j] << " ";cout << endl;}
}
void print(vector<JobNode>& v)
{for (int i = 0; i < v.size(); i++)cout << v[i].time << " ";cout << endl;
}
int main()
{int n, m;while (cin >> n>>m){priority_queue<MechineNode, vector<MechineNode>, cmp>p;vector<JobNode>v;JobNode j(-1,-1);v.push_back(j);//visit(rec);vector<vector<int>> rec(m+1,vector<int>(1,0));for (int i = 1; i <=n; i++){int time;cin >> time;JobNode j(i,time);v.push_back(j);}sort(v.begin(), v.end(),cmp1);print(v);for (int i = m; i >= 1; i--){MechineNode t(i,0);p.push(t);}for (int i=n; i>=1; i--){MechineNode t;t = p.top();//cout << "t.id:" << t.ID << " t.start: " << t.start << endl;int Mid = t.ID;if (rec[Mid].size() == 1&&rec[Mid][0]!=0)rec[Mid][0] = i;elserec[Mid].push_back(i);p.pop();t.start += v[i].time;//cout << "t.id:" << t.ID << " t.start: " << t.start << endl;t.JobId = i;p.push(t);}visit(rec);}
}
/*
7 4
5 8 7 6 10 4 2
*/