贪心算法 HDU1789 Doing Homework again
题目大意：
Ignatius有N项作业要完成。每项作业都有限期，如果不在限期内完成作业，期末考就会被扣相应的分数。给出测试数据T表示测试数，每个测试以N开始（N为0时结束），接下来一行有N个数据，分别是作业的限期，再有一行也有N个数据，分别是若不完成次作业会在期末时被扣的分数。求出他最佳的作业顺序后被扣的最小的分数。（每个作业费时一天）。
解题思路：
求被扣分数最少。这是一道贪心算法。于是第一个想法就是：使用一个结构体保存每门作业的限制时间deadline和被扣的分数reduce。
对限制时间排序，限制越大的要越先完成，若托限制时间一样，则把被扣分数大的排在前面，保证被扣分数达的要先完成。这就保证了完成的作业数做多。但是这样排序后，产生了一个问题，完成的作业数做多，被扣的分数不一定是最小，例如：
输入：7
1 4 6 4 2 4 3（每门作业的限制时间）
3 2 1 7 6 5 4（每门课若不完成期末被扣的分数）
排序后
1 2 3 4 4 4 6
3 6 4 7 5 2 1
如果只按上述排序从头去到尾则结果是7。这是因为在上面的数组中，可以选择完成（4 5），放弃（1 3）。这样才是最小的结果。
所以做法是：设一个mark数组，标记能够完成的。然后对排序后的结构体数据进行for循环，遇到
If（day<deadline（即现在的时间不超过限制时间）则表示这个作业可以完成，）
{所以day++，同时mark[i]要标记这个作业可以完成。}
Else（day>=deadline，则证明这个作业放在这里做没办法完成的。）
{
考虑在前面标记过的可完成的作业，是否有某个作业的reduce比目前的ruduce小。
If（如果有）
{则证明，可以选择完成当前的这个作业，而不完成前面reduce比当前小的作业，所以两个作业的reduce交换。}
Else（如果没有）
{则什么都不操作，进入下一次循环}
}
仅供参考。
Code：
#include<stdio.h>
#include<algorithm>
using namespace std;
struct HomeWork
{
int deadline;
int reduce;
}hw[1005];
bool mark[1005];
int t;int n;
int search(HomeWork a[],int x,int len)
{
int i,pl=-1,min=x;
for(i=0;i<len;i++)
if(mark[i]==true&&a[i].reduce<min)
{
min=a[i].reduce;
pl=i;
}
return pl;
}
bool cmp(HomeWork a ,HomeWork b)
{
if(a.deadline!=b.deadline)
return a.deadline<b.deadline;
else
return a.reduce>b.reduce;
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(mark,0,sizeof(mark));
memset(hw,0,sizeof(hw));
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&hw[i].deadline);
for(i=0;i<n;i++)
scanf("%d",&hw[i].reduce);
sort(hw,hw+n,cmp);
int day=0,reduced=0,tmp;
for(i=0;i<n;i++)
{
if(day<hw[i].deadline)
{
day++;mark[i]=true;
}
else
{
int ex=search(hw,hw[i].reduce,i);
if(ex!=-1)
{
tmp=hw[ex].reduce;
hw[ex].reduce=hw[i].reduce;
hw[i].reduce=tmp;
}
reduced+=hw[i].reduce;
}
}
printf("%d/n",reduced);
}
return 0;
}