Ignatius剛剛從第30屆ACM / ICPC回到學(xué)校。現(xiàn)在他有很多作業(yè)要做。每個(gè)老師給他一個(gè)截止作業(yè)的截止日期。如果Ignatius在截止日期之后進(jìn)行了家庭作業(yè)，老師將減少他的最終考試成績。現(xiàn)在我們假設(shè)做每個(gè)老師的作業(yè)總是需要一天的時(shí)間。以Ignatius希望你幫他安排做作業(yè)的順序來減少分?jǐn)?shù)的減少。

輸入

每個(gè)測試用例從正整數(shù)N（1 <= N <= 1000）開始，表示作業(yè)數(shù)。然后兩行。 第一行包含N個(gè)整數(shù)，表示作業(yè)的期限，下一行包含N個(gè)整數(shù)，表示減少的分?jǐn)?shù)。
輸出

對于每個(gè)測試用例，應(yīng)該輸出減少的最小總分?jǐn)?shù)，每個(gè)測試用例一行。

Sample Input

3 3 3 3 3 10 5 1 3 1 3 1 6 2 3 7 1 4 6 4 2 4 3 3 2 1 7 6 5 4

Sample Output

0 3 5
Ignatius比賽回來之后，每位老師給Ignatius一個(gè)交作業(yè)的最后期限，如果交不上去就扣分。每門作業(yè)都要一天時(shí)間完成，求最少扣多少分。先輸入一個(gè)T表示有T組測試數(shù)據(jù)，接下來每組數(shù)據(jù)先輸入一個(gè)N，代表有N個(gè)作業(yè)，然后輸入兩行，第一行表示每門作業(yè)要交的日期，第二行表示對應(yīng)的如果不交這門作業(yè)要扣的分?jǐn)?shù)。輸出要扣的最少分?jǐn)?shù)。 1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 int dayline; 5 int descore; 6 bool flag; 7 }homework[1005]; 8 bool cmp(node a,node b) 9 { 10 if(a.dayline!=b.dayline) 11 return a.dayline < b.dayline; /*按期限從短到長排序*/ 12 else 13 return a.descore>b.descore; /*如果期限相同，按被扣分?jǐn)?shù)從高到低來排序*/ 14 } 15 16 int main() 17 { 18 int t,n,temp; 19 while(cin>>t) 20 { 21 while(t--) 22 { 23 scanf("%d",&n); /*作業(yè)的數(shù)量*/ 24 for(int i = 0; i < n; i++) /*讀取作業(yè)的期限*/ 25 scanf("%d",&homework[i].dayline); 26 for(int i = 0; i < n; i++) /*讀取未完成作業(yè)被扣除的分?jǐn)?shù)*/ 27 { 28 scanf("%d",&homework[i].descore); 29 homework[i].flag = true; /*標(biāo)記可完成*/ 30 } 31 32 sort(homework,homework+n,cmp); 33 int ans = 0; /*統(tǒng)計(jì)被扣除的分?jǐn)?shù)*/ 34 int day = 1; /*截止日期*/ 35 for(int i = 0; i < n; i++) 36 { 37 if(homework[i].dayline >= day) 38 day++; 39 else{ 40 int p = homework[i].descore; 41 int temp = i; 42 for(int j =0; j < i; j++) /*往前面搜索，查找是否有被扣分?jǐn)?shù)較小的*/ 43 if(homework[j].descore < p && homework[j].flag) /*被扣分?jǐn)?shù)較少 并且是可完成的（用來完成被扣分較大的作業(yè)）*/ 44 { 45 p = homework[j].descore; 46 temp = j; 47 } 48 49 ans += p; 50 homework[temp].flag = false; /*標(biāo)記不可完成*/ 51 } 52 53 54 } 55 cout<<ans<<endl; 56 } 57 } 58 return 0; 59 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/jj81/p/7381879.html

總結(jié)

以上是生活随笔為你收集整理的ACM Doing Homework again的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。