每天做一份作业,给出每份作业的deadline和分值,求在最好策略下扣的分值最少的情况。


首先根据作业的分值从大到小排序,如果分值相同,则时间小的排在前面。

之后按顺序将作业放在deadline的那一天, 比如有一份作业的期限是3天,就将他放在第三天来做,

如果第三天已经放了作业,就往前安排,如果第一第二天都满了,这份作业就只能被扣分了。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stdio.h>
#include <cstring>
using namespace std;

class Homework{
public:
	int t,v;

	int operator <(const Homework &a) const
		{
			return (v>a.v||(v==a.v&&t<a.t));
		}
};
Homework work[1002];
int take[1002];
int main()
{
	int num,a;
	cin>>num;
	while(num--)
	{
		cin>>a;
		memset(take,0,sizeof(take));
		for(int i=1;i<=a;i++)
		{
			cin>>work[i].t;


		}
		for(int i=1;i<=a;i++)
		{
			cin>>work[i].v;
		}
		sort(work+1,work+a+1);
		int ans=0;
		for(int i=1;i<=a;i++)
		{
			bool ok=false;
				for(int k=work[i].t;k>=1;k--)
				{
					if(take[k]==0)
					{
						take[k]=1;
						ok=true;
						break;
					}
				}
				if(!ok) ans+=work[i].v;

		}
		cout<<ans<<endl;



	}
}


Logo

华为开发者空间,是为全球开发者打造的专属开发空间,汇聚了华为优质开发资源及工具,致力于让每一位开发者拥有一台云主机,基于华为根生态开发、创新。

更多推荐