【蓝桥杯】任务系统

题目

蒜头君设计了一个任务系统。这个系统是为了定时提醒蒜头君去完成一些事情。

系统大致如下，初始的时候，蒜头君可能会注册很多任务，每一个任务的注册如下:

Register Q_num Period

表示从系统启动开始，每过 <math> <semantics> <mrow> <mi> P </mi> <mi> e </mi> <mi> r </mi> <mi> i </mi> <mi> o </mi> <mi> d </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> Period </annotation> </semantics> </math>Period 秒提醒蒜头君完成编号为 <math> <semantics> <mrow> <msub> <mi> Q </mi> <mrow> <mi> n </mi> <mi> u </mi> <mi> m </mi> </mrow> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> Q_{num} </annotation> </semantics> </math>Qnum​ 的任务。

你能计算出蒜头君最先被提醒的 <math> <semantics> <mrow> <mi> k </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> k </annotation> </semantics> </math>k 个任务吗？

输入格式

第一行输入 <math> <semantics> <mrow> <mi> n </mi> <mo> ( </mo> <mn> 0 </mn> <mo> &lt; </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 3000 </mn> <mo> ) </mo> <mi mathvariant="normal"> ​ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n(0 &lt; n \le 3000)​ </annotation> </semantics> </math>n(0<n≤3000)​， <math> <semantics> <mrow> <mi> k </mi> <mo> ( </mo> <mn> 0 </mn> <mo> &lt; </mo> <mi> k </mi> <mo> ≤ </mo> <mn> 10000 </mn> <mo> ) </mo> <mi mathvariant="normal"> ​ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> k(0 &lt; k \le 10000)​ </annotation> </semantics> </math>k(0<k≤10000)​，其中 <math> <semantics> <mrow> <mi> n </mi> <mi mathvariant="normal"> ​ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n​ </annotation> </semantics> </math>n​ 表示蒜头君注册的任务数量。

接下来 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n </annotation> </semantics> </math>n 行，每行输入一条注册命令，其中 <math> <semantics> <mrow> <mn> 0 </mn> <mo> &lt; </mo> <msub> <mi> q </mi> <mrow> <mi> n </mi> <mi> u </mi> <mi> m </mi> </mrow> </msub> <mo> ≤ </mo> <mn> 3000 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 0 &lt; q_{num} \le 3000 </annotation> </semantics> </math>0<qnum​≤3000， <math> <semantics> <mrow> <mn> 0 </mn> <mo> ≤ </mo> <mi> P </mi> <mi> e </mi> <mi> r </mi> <mi> i </mi> <mi> o </mi> <mi> d </mi> <mo> ≤ </mo> <mn> 3000 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 0 \le Period \le 3000 </annotation> </semantics> </math>0≤Period≤3000。

输出格式

顺序输出 <math> <semantics> <mrow> <mi> k </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> k </annotation> </semantics> </math>k 行，表示依次提醒的任务的编号。

如果同一时间有多个任务，最先提醒编号小的任务。

样例输入

5

Register 2004 200

Register 2005 300

样例输出

2004

2005

2004

2004

2005

题解

以 Period 为初始值，每次出队 Period 最小的一组任务，再将 Period 加上初始值入队

#include<iostream>
#include<queue>
using namespace std;
struct inf{
	int Q_num;
	int Period;
	int init; // 初始 
	bool operator < (const inf & a)const{  // 重载 从小到大 
		if(Period != a.Period)
			return Period > a.Period;
		return Q_num > a.Q_num;
	}
};
int main(){
	priority_queue<inf> q;
	int n,k;
	inf tmp;
	string str;
	int tQ_num;
	int tPeriod;
	cin>>n>>k;
	while(n--){
		cin>>str>>tQ_num>>tPeriod;
		tmp.Q_num = tQ_num;
		tmp.Period = tPeriod;
		tmp.init = tPeriod;
		q.push(tmp);
	}
	while (k--) {
		tmp = q.top();
		q.pop();
        cout<<tmp.Q_num<<endl;
        tmp.Period += tmp.init;
        q.push(tmp);
    }
	return 0;
}

返回目录，查看更多