生活随笔
收集整理的這篇文章主要介紹了
HDU 1789 Doing Homework again （贪心）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
http://blog.csdn.net/dgq8211/article/details/7538060
題目鏈接：Click here~~
題意：
有 n 門作業(yè)，每門作業(yè)都有自己的截止期限，當(dāng)超過截止期限還沒有完成作業(yè)，就會扣掉相應(yīng)的分數(shù)。問如何才能使扣分最少。
解題思路：
把 n 門作業(yè)按分數(shù)從大到小排序，然后每次都把作業(yè)安排在離它的截止期限最近的一天，并把此天標記為已用，若不能安排，則扣分。
[cpp]?view plaincopy
#include?<stdio.h>?? #include?<string.h>?? #include?<algorithm>?? using?namespace?std;?? struct?T?? {?? ????int?score,date;?? }A[1005];?? bool?cmp(const?T&?s1,const?T&?s2)?? {?? ????return?s1.score?>?s2.score;?? }?? int?main()?? {?? ????int?z,n,ans;?? ????bool?in[1005];?? ????scanf("%d",&z);?? ????while(z--)?? ????{?? ????????memset(in,0,sizeof(in));?? ????????ans?=?0;?? ????????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);?? ????????for(int?i=0;i<n;i++)?? ????????{?? ????????????int?j;?? ????????????for(j?=?A[i].date;j?>=?1;j--)?? ????????????{?? ????????????????if(!in[j])?? ????????????????{?? ????????????????????in[j]?=?true;?? ????????????????????break;?? ????????????????}?? ????????????}?? ????????????if(!j)?? ????????????????ans?+=?A[i].score;?? ????????}?? ????????printf("%d\n",ans);?? ????}?? ????return?0;?? } ?
總結(jié)
以上是生活随笔為你收集整理的HDU 1789 Doing Homework again （贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
