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