学步园

ZOJ 1012:

http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1

题目不是很难，读懂题之后觉得按开始时间排序，相同时间的按酬劳排序，依次处理即可。

其实我不太明白也不能证明，为什么这种活动安排或者资源配置的题，按贪心都能解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

struct job
{
	int cpu,mem;
	int stime,etime;
	int award,extra,punlish;
	bool operator<(const job& other)const
	{
		if ( stime==other.stime )
			return award>other.award;
		else
			return stime<other.stime;
	}
};

int fTime;
int m,n,l;
int ans;
int nCase;

job jobs[10005];
int finish[10005];


void solve()
{
	ans=0;
	int i=0;
	int curTime=jobs[0].stime;
	int first=curTime;
	int ccpu=m,cmem=n;
	for(;curTime<fTime;curTime++)
	{
		ccpu=m;cmem=n;
		for (i=0;i<l;i++)
		{
			if(jobs[i].stime>curTime)
				break;
			if (!finish[i]&&ccpu>=jobs[i].cpu&&cmem>=jobs[i].mem)
			{
				finish[i]=1;
				ccpu-=jobs[i].cpu;
				cmem-=jobs[i].mem;
				ans+=jobs[i].award;
				if (curTime+1<=jobs[i].etime)
					ans+=jobs[i].extra*(jobs[i].etime-curTime-1);
				else
					ans-=jobs[i].punlish*(-jobs[i].etime+curTime+1);
			}
		}
	}
	for(i=0;i<l;i++)
	{
		if(jobs[i].stime>fTime)
			break;
		if (!finish[i] && jobs[i].etime<fTime)
		{
			ans-=jobs[i].punlish*(fTime-jobs[i].etime);
		}
	}
	printf("Case %d: %d\n\n",nCase,ans);
}
void init()
{
	memset(finish,0,sizeof(finish));
	scanf("%d%d%d",&m,&n,&l);
	for(int i=0;i<l;i++)
	{
		job& j=jobs[i];
		scanf("%d%d%d%d%d%d%d",&j.cpu,&j.mem,&j.stime,&j.etime,&j.award,&j.extra,&j.punlish);
	}
	sort(&jobs[0],&jobs[l]);
}
int main()
{
	nCase=0;
	while(scanf("%d",&fTime)&&fTime!=0)
	{
		nCase++;
		init();
		solve();
	}
}

 ZOJ1076:

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=76

题目其实就是活动安排，比较简单，当然也可以看做求最长递增子序列。

#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;

struct gene
{
	int start,end;
	int idx;
	bool operator<(const gene& other)const
	{
	//	if ( end==other.end )
		//	return start<other.start;
		return end<other.end;
	}
};

gene gens[1005];
int use[1005];
int n;

int main()
{
	while(scanf("%d",&n)&&n)
	{
		memset(use,0,sizeof(use));
		int i;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&gens[i].start,&gens[i].end);
			gens[i].idx=i+1;
		}
		sort(gens,gens+n);

		use[0]=1;
		int time=gens[0].end;
		for(i=1;i<n;i++)
		{
			if(gens[i].start>time)
			{
				use[i]=1;
				time=gens[i].end;
			}
		}

		printf("%d",gens[0].idx);
		for(i=1;i<n;i++)
			if(use[i])
				printf(" %d",gens[i].idx);
		printf("\n");
	}
}