任务调度(Schedule)

技术任务调度(Schedule) 任务调度(Schedule)清华OJ——数据结构与算法实验(中国石油大学)Description
A HPS cluster is equipped with a un

任务调度(附表)

清华OJ——数据结构与算法实验(中国石油大学)

Description

噬血细胞综合征集群配备了独特的任务调度器。简单来说,假设这个集群不支持多个任务同时运行,那么任何时候都只允许一个任务处于运行状态。最初,每个任务的优先级由一个称为优先级数的整数表示。较小的优先级数字代表高优先级。如果两个任务具有相同的任务编号,则优先级按照任务名称的美国信息交换标准代码顺序决定。遵循此策略,资源(如中央处理器)总是被优先级最低的任务占用。当一个任务完成时,选择其余任务中优先级最低的任务来执行。完成的任务不会立即退出。优先级数加倍并放回任务集。一旦优先级数大于或等于to2^32,此任务将从任务集中删除。

给定每个任务的初始优先级设置,您的工作是预测一批任务的运行顺序。

Input

第一行包含两个整数,表示n和m .n代表初始状态下的任务数m .代表预测序列的长度。每一行都以换行符结束。在以下n行中的每一行中,都包含一个整数和一个字符串。该字符串短于8,仅包含小写字母和数字。整数是优先级数字,字符串是任务名称。整数和字符串用空格分隔。

Output

最多m行,每一行包含一个字符串。根据任务执行的顺序输出任务的名称。如果执行的任务数小于m,则输出所有执行的任务。

Example

投入

3 3

一你好

2世界

10测试

输出

你好

你好

世界

Restrictions

0=n=4,000,000

0=m=2,000,000

0初始优先级编号2^32

没有同名的任务

时间: 2秒

内存: 512兆字节

Hints

优先队列

描述

某高性能计算集群(高性能计算集群)采用的

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

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

输入

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

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

输出

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

样例

见英文题面

限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

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

不会有重名的任务

时间:2 sec

内存:512 MB

提示

优先级队列

#include cstdio
#includeiostream
#includecstring
#define N 4000050
using namespace std;
struct ss
{
    long long x;
    char y[10];
    bool operator  (const ss s)const
    {
        if(x!=s.x)return xs.x;
        if(strcmp(y,s.y)0)return 1;
        else
            return 0;
    }
};
class heap
{
private:
    ss arr[N];
    int sum_element;
    void filterup(int pos)
    {
        int fa=pos/2;
        ss value=arr[pos];
        while(pos1)
        {
            if(!(arr[fa]value))break;
            arr[pos]=arr[fa];
            pos=fa;
            fa=pos/2;
        }
        arr[pos]=value;
    }
    void filterdown(int pos)
    {
        int ch=pos*2;
        ss value=arr[pos];
        while(ch=sum_element)
        {
            if(chsum_elementarr[ch]arr[ch+1])ch++;
            if(!(valuearr[ch]))break;
            arr[pos]=arr[ch];
            pos=ch;
            ch=pos*2;
        }
        arr[pos]=value;
    }
public:
    heap()
    {
        sum_element=0;
    }
    void insert(ss value)
    {
        arr[++sum_element]=value;
        filterup(sum_element);
    }
    void pop()
    {
        if(!sum_element)return;
        arr[1]=arr[sum_element--];
        filterdown(1);
    }
    ss top()
    {
        return arr[1];
    }
    bool empty()
    {
        if(sum_element)return 0;
        return 1;
    }
    void print()
    {
        for(int i=1;i=sum_element;i++)printf("%lld %s\n",arr[i].x,arr[i].y);
    }
};
heap q;
int main()
{
   /* int n,nn;
    scanf("%d",n);
    nn=n;
    while(n--)
    {
        ss now;
        scanf("%lld %s",now.x,now.y);
        q.insert(now);
    }
    q.print();
    while(nn--)
    {
        printf("%lld %s\n",q.top().x,q.top().y);
        printf("\n");
        q.pop();
    }
*/
    int n,m;
    ss now;
    scanf("%d %d",n,m);
    while(n--)
    {
        scanf("%lld %s",now.x,now.y);
        q.insert(now);
    }
    while(!q.empty()m--)
    {
        now=q.top();
        q.pop();
        printf("%s\n",now.y);
        now.x*=2;
        if(now.x(1ll32))q.insert(now);
    }
    return 0;
}

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/121785.html

(0)

相关推荐

  • 去除衣服霉点小妙招,怎样去除衣服上面的霉点

    技术去除衣服霉点小妙招,怎样去除衣服上面的霉点家里长期存放的衣服上面都会有或大或小的霉斑,可以用以下方法去除去除衣服霉点小妙招:1、棉线衣服出现霉斑时,用绿豆芽在有霉斑的地方反复揉搓,并用清水漂洗干净,霉斑就会消除。丝绸

    生活 2021年10月21日
  • 使用最广泛的计算机所用的逻辑部件是哪个

    技术使用最广泛的计算机所用的逻辑部件是哪个本篇内容介绍了“使用最广泛的计算机所用的逻辑部件是哪个”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔

    攻略 2021年10月25日
  • 2013网游排行榜前十名,网游烧钱排行榜该怎么排

    技术2013网游排行榜前十名,网游烧钱排行榜该怎么排网游烧钱排行可以分成三档,单人投入无上限级;千万土豪级和百万富翁级2013网游排行榜前十名。单人投入无上限级:这种级别的网游有三款,在热度和规模始终确保国内畅销前列的同

    生活 2021年10月28日
  • excel标准差函数,excel标准差函数符号

    技术excel标准差函数,excel标准差函数符号AVEDEV 请参阅 返回一组数据与其均值的绝对偏差的平均值excel标准差函数,ADEDEV 用于评测这组数据的离散度。 语法 AVEDEV(number1,n

    生活 2021年10月21日
  • 如何用免费代理IP爬数据

    技术如何用免费代理IP爬数据如何用免费代理IP爬数据,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。一.前言玩爬虫的都避免不了各大网站的反爬措施限制,比较常见

    攻略 2021年10月28日
  • redis有哪些内存淘汰策略如何配置(redis中线程安全的方法)

    技术Redis中线程IO模型是什么这篇文章将为大家详细讲解有关Redis中线程IO模型是什么,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。Redis是一个单线程的应用程序,NodeJs

    攻略 2021年12月21日