任务调度（附表)

清华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;
}