算法题 Mainframe

Mainframe from ZOJ（浙大OJ） Problem Set - 1012，链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1012

题目如下：

Mr. Ronald is responsible for the administration of the mainframe in ACM (Agent on Computing of Mathematics). The agent undertakes the mathematical computing jobs from some companies, and gain the rewards after has fulfilled the jobs on the mainframe. So the mainframe is very valuable to ACM. Mr. Ronald is required to arrange the order of those jobs running on mainframe. Once a job is to run, he examines the free resources for the job. If the resources meet the job's requirement, he assigns those resources to the job. Otherwise, the job will be suspended until there are enough resources.

Because of unfamiliar with the task at first, he turned everything upside down. As time went by, he became competent on it. Moreover, he had concluded a set of byelaw as following:

1. The mainframe has M CPUs and N memories can be assigned.

2. There exists a queue for the jobs waiting to be executed. You may assume the queue is large enough to hold all the waiting jobs.

3. A job Ji which need Ai CPUs and Bi memories, reaches the queue on time Ti. The job is required to be accomplished before time Ui. After successfully completed, ACM may get Vi(\$) as the reward. If it finishes before the timeline, the extra bonus is Wi(\$) per hour. If the job is late, the punishment is Xi(\$) per hour. For example, we may assume that a job's value is 10\$, its timeline is 8, and the punishment is 2\$ per hour. If the job is completed at time 10, ACM will get 10-(10-8)*2=6\$.

4. When the job start executing, the required CPUs and memories are seized by this job, and couldn't be assigned again for the other job to be executed simultaneously. After completing the job, those resources will be released. If the resources are enough, more jobs could be executed simultaneously.

5. For the sake of the share in the mainframe's computing capability, each job will be finished just in an hour from the start of executing. You may assume each job costs exactly one hour.

6. When there are no jobs to be executed, the mainframe will be idle until a job arrives at the job queue.

7. If there are more than one jobs arrive at the queue, the more valuable job will be executed first. You may assume the values of the jobs are always unequal (Vi ！= Vj).

8. If the free CPUs or memories couldn't satisfy the requirement of the job, the job will be suspended for an hour without occupying any resources. An hour later, the resources will be examined again for this job, regardless the other jobs in the queue. If the requirement unsatisfied again, it remains suspended for the next hour, and other jobs in the queue will try to be assigned the resources. Otherwise the job will seize the required CPUs and memories and start executing.

9. When more than one jobs are suspended, the earlier arrived will try to be assigned first.

Using the byelaw, Mr. Ronald may deal with the routines very well. But now, besides the routines, ACM ask him to compute the income according to the job list. Given the timeline F, he has to calculate the jobs that had been executed or should be executed. Of course, according to job Ji, if Ui>F and the job hadn't been executed, it shouldn't been taken into account; but those which had been executed or Ui<=F should been counted. If the job hadn't been executed, it will not bring ACM any value, which means only punishment to the timeline should be calculated.

Indeed, his programming ability is not good enough, and he does not like to compute manually. So he is uneasy about it. Could you help him to solve this problem?

Input

The input contains several test cases, each of which describes the mainframe's resources and the job list. Each test case begins with a line containing a single integer F, 0 <= F <= 10000, the time line. The following line consists of three integers M, N and L (M, N, L >= 0). M is the number of CPU in the mainframe, and N is the memory size. L represents the number of jobs in the job list. There will be 10000 jobs at most.

The subsequent L lines in the test case describe the information of the jobs. The data which describing job Ji consist of 7 integers Ai, Bi, Ti, Ui, Vi, Wi, Xi. Ai and Bi indicate the requirements on CPU and memory (Ai, Bi >= 0). Ti and Ui indicate the job's arriving time and the timeline (0 <= Ti <= Ui). Vi, Wi, Xi are the reward, bonus and punishment of the job (Vi, Wi, Xi >= 0).

The input file ends with an empty test case (F=0). And this case should not be processed.

Output

Your program must compute the total income of the mainframe according to the job list. For each test case, print the case number, a colon, and a white space, then the income.

Print a blank line after each test case.

Note: Don't count the jobs which hadn't been executed, and their timelines are later than F.

Sample Input

10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0

Output for the Sample Input

Case 1: 74

思路

1. 排序
2. 模拟运行
3. 计算金钱

typedef struct Job
{
int Ai, Bi, Ti, Ui, Vi, Wi, Xi;
int is_finished,finished_time;
} Job;

排序

void sort(Job *job_list, int job_list_length)
{
Job *min, temp;
int i, ii;

for (i = 0; i < job_list_length; i++)
{
min = &job_list[i];
for (ii = i + 1; ii < job_list_length; ii++)
{
if (min->Ti > job_list[ii].Ti)
{
min = &job_list[ii];
}
else if(min->Ti == job_list[ii].Ti)
{
// 内部是为了给Vi进行排序
if(min->Vi < job_list[ii].Vi)
{
min = &job_list[ii];
}
}
}
// 进行交换
temp = job_list[i];
job_list[i] = *min;
*min = temp;
}
}

模拟运行

// 模拟CPU处理进程，time必须小于时间线
for(time =1 ;time<timeline;time++)
{
// 每个时间片都需要进行初始化
cpu = mainframe.cpu;
mem = mainframe.mem;
for(ii = 0 ;ii<job_amount;ii++)
{
// 已经完成的就不用执行了
if(job_list[ii].is_finished == 1)
{
continue;
}

// 还没到则不用执行
if(job_list[ii].Ti > time)
{
continue;
}

// 资源够分配的话，就执行
if(job_list[ii].Ai <= cpu && job_list[ii].Bi <= mem)
{
cpu -= job_list[ii].Ai;
mem -= job_list[ii].Bi;
job_list[ii].is_finished = 1;
job_list[ii].finished_time = time + 1;
}
}
}

计算金钱

// 计算金钱
money = 0;
for(i =0 ;i<job_amount;i++)
{
if(job_list[i].is_finished == 1)
{
// 要罚款的情况
if(job_list[i].finished_time > job_list[i].Ui)
{
// printf("-%d\n",(job_list[i].finished_time - job_list[i].Ui)*job_list[i].Xi);
money += job_list[i].Vi - (job_list[i].finished_time - job_list[i].Ui)*job_list[i].Xi;
}
else // 不要罚款的情况
{
// printf("+%d\n",(job_list[i].Ui - job_list[i].finished_time)*job_list[i].Wi);
money += job_list[i].Vi + (job_list[i].Ui - job_list[i].finished_time)*job_list[i].Wi;
}
}
else if(job_list[i].Ui < timeline)
{
// printf("--%d %d\n",(timeline - job_list[i].Ui)*job_list[i].Xi,job_list[i].Xi);
money -= (timeline - job_list[i].Ui)*job_list[i].Xi;
}
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Job
{
int Ai, Bi, Ti, Ui, Vi, Wi, Xi;
int is_finished, finished_time;
} Job;

void sort(Job *job_list, int job_list_length)
{
Job *min, temp;
int i, ii;

for (i = 0; i < job_list_length; i++)
{
min = &job_list[i];
for (ii = i + 1; ii < job_list_length; ii++)
{
if (min->Ti > job_list[ii].Ti)
{
min = &job_list[ii];
}
else if (min->Ti == job_list[ii].Ti)
{
// 内部是为了给Vi进行排序
if (min->Vi < job_list[ii].Vi)
{
min = &job_list[ii];
}
}
}
// 进行交换
temp = job_list[i];
job_list[i] = *min;
*min = temp;
}
}

int main()
{
int timeline, job_amount, i, time, ii, cpu, mem, money, count;
Job job_list[0x10000];

struct
{
int cpu;
int mem;
} mainframe;

// 计数器
count = 0;

while (scanf("%d", &timeline) != EOF && timeline != 0)
{
count++;
scanf("%d %d %d", &mainframe.cpu, &mainframe.mem, &job_amount);
// 输入数据
for (i = 0; i < job_amount; i++)
{
scanf("%d %d %d %d %d %d %d",
&job_list[i].Ai,
&job_list[i].Bi,
&job_list[i].Ti,
&job_list[i].Ui,
&job_list[i].Vi,
&job_list[i].Wi,
&job_list[i].Xi);
// 初始化
job_list[i].is_finished = 0;
}

// 进行排序呢
sort(job_list, job_amount);

// 模拟CPU处理进程，time必须小于时间线
for (time = 1; time < timeline; time++)
{
// 每个时间片都需要进行初始化
cpu = mainframe.cpu;
mem = mainframe.mem;
for (ii = 0; ii < job_amount; ii++)
{
// 已经完成的就不用执行了
if (job_list[ii].is_finished == 1)
{
continue;
}

// 还没到则不用执行
if (job_list[ii].Ti > time)
{
continue;
}

// 资源够分配的话，就执行
if (job_list[ii].Ai <= cpu && job_list[ii].Bi <= mem)
{
cpu -= job_list[ii].Ai;
mem -= job_list[ii].Bi;
job_list[ii].is_finished = 1;
job_list[ii].finished_time = time + 1;
}
}
}

// 计算金钱
money = 0;
for (i = 0; i < job_amount; i++)
{
if (job_list[i].is_finished == 1)
{
// 要罚款的情况
if (job_list[i].finished_time > job_list[i].Ui)
{
// printf("-%d\n",(job_list[i].finished_time - job_list[i].Ui)*job_list[i].Xi);
money += job_list[i].Vi - (job_list[i].finished_time - job_list[i].Ui) * job_list[i].Xi;
}
else // 不要罚款的情况
{
// printf("+%d\n",(job_list[i].Ui - job_list[i].finished_time)*job_list[i].Wi);
money += job_list[i].Vi + (job_list[i].Ui - job_list[i].finished_time) * job_list[i].Wi;
}
}
else if (job_list[i].Ui < timeline)
{
// printf("--%d %d\n",(timeline - job_list[i].Ui)*job_list[i].Xi,job_list[i].Xi);
money -= (timeline - job_list[i].Ui) * job_list[i].Xi;
}
}

printf("Case %d: %d\n", count, money);
puts("");
}
return 0;
}

总结

1. 调试能力很重要，没有很强的调试能力，遇到逻辑bug就很惨了。2. 取得变量名一定要有意义，不然的后一旦变量过多就很容易混淆。 3. 算法的优化非常的重要，下面是我第一次写的排序算法。和之后写的差别很大。

void sort_by_Vi(Job *job_list, int job_list_length)
{
Job *max, temp;
int i, ii;

for (i = 0; i < job_list_length - 1; i++)
{
max = &job_list[i];
for (ii = i + 1; ii < job_list_length; ii++)
{
if (max->Vi < job_list[ii].Vi)
{
max = &job_list[ii];
}
}
temp = job_list[i];
job_list[i] = *max;
*max = temp;
}
}

void sort_by_Ti(Job job_list, int job_list_length) { Job head, *min, temp; int i, ii, sign, sign_length; sign = 0; sign_length = 0;

for (i = 0; i < job_list_length; i++)
{
if (sign != job_list[i].Ti && sign != 0)
{
sign_length = 0;
}
min = &job_list[i];
for (ii = i + 1; ii < job_list_length; ii++)
{
if (min->Ti > job_list[ii].Ti)
{
min = &job_list[ii];
}
}
temp = job_list[i];
job_list[i] = *min;
*min = temp;

if (sign == 0)
{
sign = job_list[i].Ti;
}

sign_length++;
}

// 结束时，还要排序一次 