首页 > ACM题库 > HDU-杭电 > hdu 1972 Printer Queue-模拟-[解题报告]cpp:nogutter
2013
12-26

hdu 1972 Printer Queue-模拟-[解题报告]cpp:nogutter

Printer Queue

问题描述 :

The only printer in the computer science students?union is experiencing an extremely heavy workload. Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output. Because some jobs are more important than others, the Hacker General has invented and implemented a simple priority system for the print job queue. Now, each job is assigned a priority between 1 and 9 (with 9 being the highest priority, and 1 being the lowest), and the printer operates as follows.
?The first job J in queue is taken from the queue.
?If there is some job in the queue with a higher priority than job J, thenmove J to the end of the queue without printing it.
?Otherwise, print job J (and do not put it back in the queue).

In this way, all those importantmuffin recipes that the Hacker General is printing get printed very quickly. Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that� life.

Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed. You decide to write a program to figure this out. The program will be given the current queue (as a list of priorities) as well as the position of your job in the queue, and must then calculate how long it will take until your job is printed, assuming that no additional jobs will be added to the queue. To simplifymatters, we assume that printing a job always takes exactly one minute, and that adding and removing jobs from the queue is instantaneous.

输入:

One line with a positive integer: the number of test cases (at most 100). Then for each test case:
?One line with two integers n and m, where n is the number of jobs in the queue (1 <= n <= 100) and m is the position of your job (0 <= m <= n &#8722; 1). The first position in the queue is number 0, the second is number 1, and so on.
?One linewith n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

输出:

One line with a positive integer: the number of test cases (at most 100). Then for each test case:
?One line with two integers n and m, where n is the number of jobs in the queue (1 <= n <= 100) and m is the position of your job (0 <= m <= n &#8722; 1). The first position in the queue is number 0, the second is number 1, and so on.
?One linewith n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

样例输入:

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

样例输出:

1
2
5

//简单的队列模拟
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int priority[101];
struct Job
{
	int priority;
	bool yours;
}job[101];
bool cmp(int a,int b)
{
	return a > b;
}
int main()
{
	//freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,p,time = 1,pt = 0;
		memset(job,0,sizeof(Job)*100);
		queue<Job> q;
		scanf("%d%d",&n,&p);
		job[p].yours = 1;
		for(int i = 0;i < n;++i)
		{
			scanf("%d",&priority[i]);
			job[i].priority = priority[i];
			q.push(job[i]);
		}
		sort(priority,priority+n,cmp);
		while(q.front().priority != priority[pt] || !q.front().yours)
		{
			Job temp;
			temp = q.front();
			q.pop();
			if(temp.priority == priority[pt])
			{			
				pt++;
				++time;
			}
			else	q.push(temp);
		}
		
		printf("%d/n",time);
	}
	return 0;
}

解题转自:http://blog.csdn.net/chinaczy/article/details/5594040


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。