[題目]http://mp.weixin.qq.com/s/-cR07rHU91owk8nMOfhz9w
題目：任務(wù)調(diào)度在分布式調(diào)度系統(tǒng)中是一個很復(fù)雜很有挑戰(zhàn)的問題叠赐。這里我們考慮一個簡化的場景：假設(shè)一個中央調(diào)度機(jī)，有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上去執(zhí)行赛不。由于每臺服務(wù)器的配置不一樣罢洲，因此服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。
例如：有2個執(zhí)行機(jī)a, b. 執(zhí)行一個任務(wù)分別需要7min耸峭，10min，有6個任務(wù)待調(diào)度抓艳。如果平分這6個任務(wù)帚戳，即a，b各分三個任務(wù)偏友，則最短需要30min執(zhí)行完所有对供。如果a分這4個任務(wù)，b分2個鹅髓，則最短28min執(zhí)行完京景。
請設(shè)計調(diào)度算法，使得所有任務(wù)完成所需的時間最短
簡述思路
請用你熟悉的編程語言編碼實現(xiàn)以下方法醒串，輸入為m臺服務(wù)器鄙皇，每臺機(jī)器處理一個任務(wù)的時間為t[i]，完成n個任務(wù)伴逸，輸出n個任務(wù)在m臺服務(wù)器的分布：
int estimate_process_time(int[] t, int m, int n);
思路：本題是個基本的題型，考慮到如何進(jìn)行調(diào)度的問題博烂，調(diào)度問題是個非常大的問題漱竖，本題簡化了模型馍惹，該某型考慮的是如何組織計算單元， 使得計算的總時間最小悼吱。
其實良狈，學(xué)習(xí)算法直到現(xiàn)在，我基本上完成了算法的前半部分（基礎(chǔ)）遇西，就是如何去思考一個算法題，用什么行為去完成這個算法粱檀，我對后半部分漫玄，比如圖論算法，DNF算法渗常，數(shù)論算法等等汗盘，這些高級算法我還是沒有掌握，還有就是如何進(jìn)行算法分析尸执，這個內(nèi)容我也沒有掌握缓醋，很遺憾，我需要學(xué)習(xí)的東西還有很多褪贵。個人感覺計算機(jī)的知識是個很龐大的體系，要想全部掌握我想很困難脆丁，所以針對個人興趣动雹，研究某一領(lǐng)域的算法是一個不錯的選擇，但是歼培，基礎(chǔ)的算法還是要會的，畢竟萬變不離其宗躲庄。
此題，如果能想到使用小頂堆笋庄，基本上就算完成了算法了倔监。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct nt{
int n;
int t;
int i;
nt (int e1, int e2) : n(0), t(e1), i(e2) {}
};
class CCompNt
{
public:
bool operator() (nt e1, nt e2)
{
return (e2.n+1) * e2.t < (e1.n+1) * e1.t
|| ((e2.n+1) * e2.t == (e1.n+1) * e1.t && e2.t <= e1.t);
}
} CompNt;
class CCompNt2
{
public:
bool operator() (nt e1, nt e2)
{
return e1.i < e2.i;
}
} CompNt2;
void printNt(nt e)
{
cout << "(" << e.i << "," << e.t << "," << e.n << ") ";
}
vector<nt> estimate_process_time(const vector<int> & vect, int m, int n)
{
vector<nt> vecNt;
for (int i=0; i<m; ++i) {
vecNt.push_back(nt(vect[i], i));
}
make_heap(vecNt.begin(), vecNt.end(), CompNt);
for (int i=0; i<n; ++i) {
pop_heap(vecNt.begin(), vecNt.end(), CompNt);
auto nt1 = vecNt.back();
vecNt.pop_back();
nt1.n += 1;
vecNt.push_back(nt1);
push_heap(vecNt.begin(), vecNt.end(), CompNt);
}
sort(vecNt.begin(), vecNt.end(), CompNt);
return vecNt;
}
int main(int argc, char ** argv)
{
int n = 6;
int m = 2;
vector<int> t = {
7, 10
};
auto vecNt = estimate_process_time(t, m, n);
cout << "(index, t, n)" << endl;
for_each(vecNt.begin(), vecNt.end(), printNt);
return 0;
}
文章的最后丐枉，還是想吐槽一下，C語言提供的數(shù)據(jù)結(jié)構(gòu)真心的少籍嘹，C++這方面做的不錯弯院，但是C++這方面需要不斷的訓(xùn)練和學(xué)習(xí)，比如颂碘，這里設(shè)計小頂堆的時候椅挣，我對于比較算法的設(shè)計就出現(xiàn)了問題，糾結(jié)了好長時間鼠证。另外，這只是一個校招題适掰，題目的難度你們可以從代碼中感受一下荠列，代碼真的不難，難得是如何去想费就、去解決類似這樣的問題４ǘ印？寻帷艳汽！核心算法就是函數(shù)estimate_process_time中的for循環(huán)河狐，如果你用C實現(xiàn)瑟捣，那么heap的實現(xiàn)應(yīng)該也算是核心代碼了，這樣增加了解題的難度捐祠！
