GitBook

这里写图片描述 这里写图片描述

为了让浪费的分数最小 考虑优先排序分数

由题意知,尽量使安排放在靠近截止日期的那一天 比如 4 天截止 那么便考虑放在第4天完成,如果不行就第3天第2天…… 如果安排不了,说明这个分数就浪费了

所以可建数组记录当天是否有安排作业 以此来判断作业应该安排在哪一天

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node {
	int date,score;
} a[1200];
bool cmp(node A,node B) {
	if(A.score==B.score)
		return A.date>B.date;
	else
		return A.score>B.score;
}
int flag[1200];
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int n;
		scanf("%d",&n);
		for(int i=0; i<n; i++)
			scanf("%d",&a[i].date);
		for(int i=0; i<n; i++)
			scanf("%d",&a[i].score);
		sort(a,a+n,cmp);
		int sum=0;
		memset(flag,0,sizeof(flag));
		for(int i=0; i<n; i++) {
			int j;
			for(j=a[i].date; j>0; j--) {
				if(!flag[j]) {
					flag[j]=1;
					break;
				}
			}
			if(j==0)
				sum+=a[i].score;
		}
		printf("%d\n",sum);
	}
	return 0;
}

题目地址:【杭电】[1789]Doing Homework again