任务调度(Schedule)

描述

某高性能计算集群(HPC cluster)采用的任务调度器与众不同。为简化起见,假定该集群不支持多任务同时执行,故同一时刻只有单个任务处于执行状态。初始状态下,每个任务都由称作优先级数的一个整数指定优先级,该数值越小优先级越高若优先级数相等,则任务名ASCII字典顺序低者优先。此后,CPU等资源总是被优先级数最小的任务占用;每一任务计算完毕,再选取优先级数最小下一任务。不过,这里的任务在计算结束后通常并不立即退出,而是将优先级数加倍(加倍计算所需的时间可以忽略)并继续参与调度;只有在优先级数不小于2^32时,才真正退出

你的任务是,根据初始优先级设置,按照上述调度原则,预测一批计算任务的执行序列。

 

 

输入

第一行为以空格分隔的两个整数n和m,n为初始时的任务总数,m为所预测的任务执行序列长度,每行末尾有一个换行符

以下n行分别包含一个整数和一个由不超过8个小写字母和数字组成的字符串。前者为任务的初始优先级数,后者为任务名。数字和字符串之间以空格分隔

 

 

输出

最多m行,各含一个字符串。按执行次序分别给出执行序列中前m个任务的名称,若执行序列少于m,那么输出调度器的任务处理完毕前的所有任务即可。

 

 

输入样例

3 3

1 hello

2 world

10 test

 

 

输出样例

hello

hello

world

 

 

限制

0 ≤ n ≤ 4,000,000  

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

不会有重名的任务

时间:2s,内存:512MB

 

 

 

   这道题我记得书上有提到过 优先权队列 ,赶紧把数据结构的书翻出来看看,上面说优先权队列一般用堆,即堆排序实现~~好吧,自己把以前写的堆排序程序改改~~(对了,以后有时间把我准备考研的这段时间写的代码也都发上来~~)~~核心思想是用最小堆;再自己写个比较大小的函数,让它先比较优先权,一样的话比较任务名~~然后输出堆顶元素的任务名后堆的规模暂时不减小,先把其优先权*2,等超出限定了再把后面的元素与其交换;等后面的元素都换没了,再减小堆的规模~~

 

 

//构造最小堆,自定义两个元素的比较函数
#include

using namespace std;

struct Schedule
{
   long long priority;
   string name;
}schedules[4000001];

template
void Swap(T *a,T *b)
{
   T temp=*a;
   *a=*b;*b=temp;
}

bool smaller(Schedule A,Schedule B)
{
   if(A.priority    else if(A.priority>B.priority) return false;
       else
       {//相等的情况
           if(A.name            else {return false;}
       }
}

void AdjustDownMin(Schedule A[],int i,int n)  //堆排序的指定某点向下调整,最小堆,i为要调整序号,从0开始,n为有n个元素
{
   int lchild=2*i+1;int min=4000001;    //i左孩子的位置,
   if(lchild        if(lchild+1        {
           //cout<<"lchild+1="<            if( smaller(A[lchild],A[lchild+1]) ) min=lchild;
           else min=lchild+1;
       }
       else min=lchild;
       if( smaller(A[min],A[i]) )
       {
           Swap(&A[i],&A[min]);
           AdjustDownMin(A,min,n);
       }
   }
}

void HeapSort(Schedule A[],int n,int m)  //堆排序,最小堆,n为有n个元素
{
   int i,j=n;
   for(i=(n-2)/2;i>-1;i–) {AdjustDownMin(A,i,n);}  //从最后一个非叶子结点开始依次向前扫描,依次做向下调整,即可完成构建最大最小堆
   for(i=n-1;i>-1; )
   {
       cout<        Swap(&A[0],&A[i]);  //交换堆顶和堆底元素,
       if( A[i].priority>=4294967296 ) //2^32=4294967296
       {
           if(j            else i–;
       }
       AdjustDownMin(A,0,i+1);  //此时刚交换完,只有A[0]是无序的,其他都是有序的,所以只需对A[0]进行向下调整,既可重获最大堆。此时,调整的范围由于已输出了一个,所以要减一,用i就行
   }
}

int main()
{
   int n,m,i;
   cin>>n>>m;
   for(i=0;i    {
       cin>>schedules[i].priority>>schedules[i].name;
   }
   HeapSort(schedules,n,m);

   return 0;
}

 

 

 

   但是交到OJ上只跑出来一组对的,其余的全是超时~~为毛线啊?到底哪里还能优化?~~据群里人说是清华OJ本身的问题,清华OJ是用虚拟机的,所以导致所有的io接口操作巨慢~~听说有人写了个在内存里模拟io交换的外挂,可以大大提高清华OJ的跑分的速度项~~但是外挂在哪儿呢~~

 

另外:我觉得题目给的输出样例是不是不完整?题目给的优先级界限是2^32,那怎么也不可能只输出3组呀~~

 

 

 

   呜~~我把题目给看错了~~题目是要n个进程一起排,然后只输出前m组结果~~我看成有个m个进程的进程池,每次运行n个了~~~

   好吧~~改过的程序如下~~

 

//构造最小堆,自定义两个元素的比较函数
#include

using namespace std;

struct Schedule
{
   long long priority;
   string name;
}schedules[4999999];

template
void Swap(T *a,T *b)
{
   T temp=*a;
   *a=*b;*b=temp;
}

bool smaller(Schedule A,Schedule B)
{
   if(A.priority    else if(A.priority>B.priority) return false;
       else
       {//相等的情况
           if(A.name            else {return false;}
       }
}

void AdjustDownMin(Schedule A[],int i,int n)  //堆排序的指定某点向下调整,最小堆,i为要调整序号,从0开始,n为有n个元素
{
   int lchild=2*i+1;int min=4999999;    //i左孩子的位置,
   if(lchild        if(lchild+1        {
           //cout<<"lchild+1="<            if( smaller(A[lchild],A[lchild+1]) ) min=lchild;
           else min=lchild+1;
       }
       else min=lchild;
       if( smaller(A[min],A[i]) )
       {
           Swap(&A[i],&A[min]);
           AdjustDownMin(A,min,n);
       }
   }
}

void HeapSort(Schedule A[],int n,int m)  //堆排序,最小堆,n为有n个元素
{
   int i,j=n,k=0;
   for(i=(n-2)/2;i>-1;i–) {AdjustDownMin(A,i,n);}  //从最后一个非叶子结点开始依次向前扫描,依次做向下调整,即可完成构建最大最小堆
   for(i=n-1;i>-1; )
   {
       cout<        //Swap(&A[0],&A[i]);  //交换堆顶和堆底元素,
       if( A[0].priority>=4294967296 ) //2^32=4294967296
       {
           //if(j            //else i–;
           Swap(&A[0],&A[i]);
           i–;
       }
       AdjustDownMin(A,0,i+1);  //此时刚交换完,只有A[0]是无序的,其他都是有序的,所以只需对A[0]进行向下调整,既可重获最大堆。此时,调整的范围由于已输出了一个,所以要减一,用i就行
   }                               //i+1个元素
}

int main()
{
   int n,m,i;
   cin>>n>>m;
   for(i=0;i    {
       cin>>schedules[i].priority>>schedules[i].name;
   }
   HeapSort(schedules,n,m);

   return 0;
}

 

   最后是跑出来7组数据~~中间有一组错误,好奇怪~~~~后12组全部超时~~~好吧~清华肯定有另外更好的方案~~我这个建最小堆的已经没什么需要改进了的吧?~~

任务调度(Schedule)》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注