題目原文：http://acm.hdu.edu.cn/showproblem.php?pid=1789
題目大意：要在指定的日期內完成作業(yè)，并且每個作業(yè)只需要1天的時間并且每天只能做一個作業(yè)，沒完成的就會扣相應的學分，要求被扣最少的學分。
題目分析：
起初我是這樣想得：
1。如果在指定的日期內完成則不會扣分，且每個作業(yè)只需要一天完成，那么肯定會想到先把學分多的先做，是不是這樣就能行呢,先看一組例子吧：
1 4 6 4 2 4 3
3 2 1 7 6 5 4
如果只考慮學分多的先做那么排列就會是：7654321 ，但這并不是最優(yōu)的安排。
2。換個角度想了想，要使扣分少，我應該盡量使扣分少的過期在做，最好要讓學分多的在它指定的那天完成，這樣就會使得這天被扣分數(shù)盡量少。
結果思路就出來了： 1。先處理分數(shù)多的作業(yè)，把分數(shù)多的安排在它最后期限那一天。
2。如果那天被占用了，就往前一天安排。
3。如果前面沒有日期了，就安排最后那天處理這個作業(yè)。此時就要扣掉對應的學分。
算法設計：1。利用STL中的sort()進行排序，但是因為定義了一個數(shù)據(jù)結構，需要重新寫個判斷函數(shù)。
2。定義一個vist[]數(shù)組來標記該天是否被安排
代碼設計如下：
#include "iostream"
#include <algorithm> //need sort()
using namespace std;
struct Homwo //作頁日期和分數(shù)的結構
{
int date;
int score;
}p[10002];
//以分數(shù)排名
bool cmp(const Homwo m,const Homwo n)
{
return m.score>n.score?1:0;
}
int main()
{
int t;
cin>>t;
while (t—)
{
int n;
int vist[10002]={0};
int flag,k=0;
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>p[i].date;
}
for (i=1;i<=n;i++)
{
cin>>p[i].score;
}
sort(p+1,p+n+1,cmp);//注意數(shù)組時從1開始的！按學分排列
for (i=1;i<=n;i++)
{
if(vist[p[i].date]==0) vist[p[i].date]=1;
else
{
for (int j=p[i].date-1,flag=0;j>0;j--)
{
if(vist[j]==0)
{ vist[j]=1;
flag=1;
break;
}
}
if (flag==0)
{
for (j=n;j>p[i].date;j--)
{
if(vist[j]==0)
{
vist[j]=1;
k=k+p[i].score;
break;
}
}
}
}
}
cout<<k<<endl;
}
return 0;
}