題意：
? ? ? 有N個任務(wù)，每個任務(wù)都有自己的時間間隔（就是每t秒請求執(zhí)行一次）和任務(wù)id，這n個任務(wù)公用一個cpu，每次我們都執(zhí)行時間靠前的，如果相同時間內(nèi)有多個任務(wù)，就執(zhí)行任務(wù)id小的，要求模擬出執(zhí)行的前n個任務(wù)都是誰。


思路：
? ? ?這個是不是就是操作系統(tǒng)里的FCFS算法啊！這個要模擬可以用優(yōu)先隊列去做，開一個結(jié)構(gòu)體，有三個變量，一個是id,一個是時間間隔t,另一個是總時間st,每次取出都是按照a.st > b.st || a.st == b.st && a.id > b.id (這里是優(yōu)先隊列里的寫法，不要誤會) ? 一開始把所有的任務(wù)都進(jìn)隊列此時st=t，然后取出一個最小的作為第一個任務(wù)，然后把取出來這個的a.st+=a.t之后進(jìn)隊列，就這樣反復(fù)執(zhí)行，執(zhí)行n次就行了，這個方法叫做多路歸并問題，比較簡單，而且容易想到和理解。


?


#include<queue>
#include<stdio.h>


using namespace std;


typedef struct NODE
{
? ?int youxianji ,time ,_time;
? ?friend bool operator < (NODE a ,NODE b)
? ?{
? ? ? return a.time > b.time || a.time == b.time && a.youxianji > b.youxianji;
? ?}
}NODE;


NODE tou ,xin;


int main ()
{
? ? char str[10];
? ? int i ,k;
? ? priority_queue<NODE>q;
? ? while(scanf("%s" ,str) && str[0] != '#')
? ? {
? ? ? ? scanf("%d %d" ,&xin.youxianji ,&xin.time);
? ? ? ? xin._time = xin.time;
? ? ? ? q.push(xin); ? ? ? ? ? ? ? ??
? ? }
? ? scanf("%d" ,&k);
? ? while(k--)
? ? {
? ? ? ?tou = q.top();
? ? ? ?q.pop();
? ? ? ?printf("%d\n" ,tou.youxianji);
? ? ? ?xin = tou;
? ? ? ?xin.time += xin._time;
? ? ? ?q.push(xin);
? ? }
? ? return 0; ??
}
? ? ? ? ??

總結(jié)

以上是生活随笔為你收集整理的LA3135简单多路归并（优先队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。