任务调度

2014年4月25日3,5160

来源：http://nnsznoi.openjudge.cn/greedy/0014/

Description

一个单位时间任务是一个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;……。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:
1.包含n个单位时间任务的集合S={1,2,……,n};
2.n个取整的期限d1,……,dn,(1≤d,≤n),任务i要求在di前完成;
3.n个非负的权(或罚款)w1,……,wn。如果任务i没在时间di之前结束,则导致罚款wi;
要求找出S的一个调度,使之最小化总的罚款。

Input

输入第一行为N<=1000，后面N行每行两个数，即为对应的di与wi。(wi<=1000)

Output

输出最小总罚款

Sample Input

1 4

2 4

2 8

3 8

5 2

Sample Output

4

跟任务安排一样还不用堆，因为有人问。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
struct data{int d,w;}a[1001];
int n,ans,b[1001],now;
bool cmp(data a,data b)
{return a.d<b.d;}
int findmn()
{
	int mn=inf,tmp;
	for(int i=1;i<=now;i++)
	   if(b[i]<mn){mn=b[i];tmp=i;}
	return tmp;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	   scanf("%d%d",&a[i].d,&a[i].w);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(now<a[i].d){now++;b[now]=a[i].w;}
		else 
		{
			int t=findmn();
			if(b[t]<a[i].w){ans+=b[t];b[t]=a[i].w;}
			else ans+=a[i].w;
		}
	}
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#define inf 0x7fffffff

using namespace std;

struct data{int d,w;}a[1001];

int n,ans,b[1001],now;

bool cmp(data a,data b)

{return a.d<b.d;}

int findmn()

{

int mn=inf,tmp;

for(int i=1;i<=now;i++)

if(b[i]<mn){mn=b[i];tmp=i;}

return tmp;

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%d%d",&a[i].d,&a[i].w);

sort(a+1,a+n+1,cmp);

for(int i=1;i<=n;i++)

{

if(now<a[i].d){now++;b[now]=a[i].w;}

else

{

int t=findmn();

if(b[t]<a[i].w){ans+=b[t];b[t]=a[i].w;}

else ans+=a[i].w;

}

printf("%d",ans);

return 0;

}

« 「CF413C」Jeopardy! 「CF425A」Sereja and Swaps »

hzwer.com _ Home | http://hzwer.com

任务调度

分类目录

热门文章

Myfriends

近期评论