[数据结构与算法]HDU-1789题解

题目链接

Problem - 1789 (hdu.edu.cn)

?

题目大意

一共t组测试数据，对于每组测试数据，第一行给出n门作业的ddl，第二行给出对应功作业若在限制时间内未完成需要扣除的分数，题目假定一天只能完成一门作业，问怎样安排作业的完成顺序，可以使得扣除的分数最小。

?

解题思路

首先对分数从大到小排序，若分数相同，则ddl小的排在前面。对于一门功作业，我们自然是希望越晚完成越好（能拖则拖），所以我们只需对排位序的n门作业，从第一门开始枚举，根据每个人都有的惰性，自然是能拖到截止期是最好不过了（ddl是第一生产力），若ddl当天不能完成则推到前一天完成，若前一天已经有了安排则再往前推一天…

如此安排之后，若发现一门功课必须第0天完成，那显然是完成不了的作业，所以累加对应作业扣除的分数，即可得到解。

?

代码

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

const int N = 1e4 + 10;
struct subject
{
	int ddl;
	int rscore;
}sub[N];

bool cmp(subject a, subject b)         //排序规则
{
	if (a.rscore != b.rscore)
		return a.rscore > b.rscore;
	return a.ddl < b.ddl;
}
int hashTable[N];   //用来记录可以完成的作业

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int t, n;
	cin >> t;
	while (t--)
	{
		memset(hashTable, 0, sizeof(hashTable));			//hashTable数组初始化位为0表示当天没有作业安排
		cin >> n;
		int rsum = 0, hashsum = 0;         //rsum用来记录n门作业的分数之和，hashsum用来记录可以在ddl前完成的作业分数之和
		for (int i = 1; i <= n; i++)
			cin >> sub[i].ddl;
		for (int i = 1; i <= n; i++)
		{
			cin >> sub[i].rscore;
			rsum += sub[i].rscore;
		}

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

		for (int i = 1; i <= n; i++)
		{
			if (!hashTable[sub[i].ddl])					//如果为0表示当天没有作业安排
			{
				hashTable[sub[i].ddl] = sub[i].rscore;		//故更新hashTable对应的值
				hashsum += sub[i].rscore;
			}
			else//若不为0，表示当天已有安排，则往前推
			{
				int tot = sub[i].ddl - 1;
				while (hashTable[tot] && tot > 0)
					tot--;
				if (tot != 0)
				{
					hashTable[tot] = sub[i].rscore;
					hashsum += sub[i].rscore;
				}
			}
		}

		cout << rsum - hashsum << endl;
	}
	return 0;
}

?

心得体会

这道题读完题目很明显可以看出是贪心，不过我做的时候卡了很久，而且还WA了两次，做了两次之后仔细检查才发现数组越界了，输入时是[1,n]，排序时是[0,n)，这提醒我时刻要注意访问非法内存等问题，一个小小的问题可能需要花费大量的时间debug。