期末考試(優先隊列)

期末考試

時間限制：1000 ms  |  記憶體限制：65535 KB

難度：2

描述

馬上就要考試了，小T有許多作業要做，而且每個老師都給出來了作業要交的期限，如果在規定的期限内沒

交作業就會扣期末成績的分數，假設完成每門功課需要一天的時間，你能幫助小T扣除的分數最小嗎？

輸入

輸入n，表示n門功課(n<2000)，接下來n行，每行兩個數a，b，分别表示交作業的最後期限，遲交扣除的分數。

(以檔案結尾)

輸出

輸出扣除的最小分數。

樣例輸入

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

樣例輸出

0
3
5      

題解：sort先排序，然後判斷扣分值，先做分高的；優先隊列從小到大，長度代表天；

代碼：

1 #include<stdio.h>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 struct Node{
 7     int time,score;
 8 };
 9 int cmp(Node a,Node b){
10     if(a.time!=b.time)return a.time<b.time;
11     else return a.score>b.score;
12 }
13 Node m[2010];
14 int main(){
15     int n,day,tot;
16     while(scanf("%d",&n),n){priority_queue<int,vector<int>,greater<int> >work;tot=0;
17     memset(m,0,sizeof(m));
18         for(int i=0;i<n;++i)scanf("%d%d",&m[i].time,&m[i].score);
19         sort(m,m+n,cmp);
20         for(int i=0;i<n;++i){day=work.size();
21             if(m[i].time>day)work.push(m[i].score);
22             else{
23                 if(!work.empty()&&m[i].score>work.top())tot+=work.top(),work.pop(),work.push(m[i].score);
24             else tot+=m[i].score;
25             }
26         }
27         printf("%d\n",tot);
28     }
29     return 0;
30 }      

Doing Homework again

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 66   Accepted Submission(s) : 44

Problem Description

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test. And now we assume that doing everyone homework always takes one day. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.

Input

The input contains several test cases. The first line of the input is a single integer T that is the number of test cases. T test cases follow. Each test case start with a positive integer N(1<=N<=1000) which indicate the number of homework.. Then 2 lines follow. The first line contains N integers that indicate the deadlines of the subjects, and the next line contains N integers that indicate the reduced scores.

Output

For each test case, you should output the smallest total reduced score, one line per test case.

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

 題解，兩道題差不多：

1 #include<stdio.h>
 2 #include<math.h>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Node{
 6     double s,e;
 7 };
 8 int n,d,k;
 9 Node area[1010];
10 int cmp(Node a,Node b){
11     return a.e<b.e;
12 }
13 int change(int x,int y){
14     if(y>d)return 0;
15     double a,b,m=sqrt(d*d-y*y);
16     a=x-m;b=x+m;
17     area[k].s=a;area[k].e=b;k++;
18     return 1;
19 }
20 int main(){int t,x,y,flot,temp,num,l=0;
21     while(scanf("%d%d",&n,&d),n||d){k=0;flot=1;temp=0;num=1;l++;
22             for(int i=0;i<n;i++){
23                 scanf("%d%d",&x,&y);
24                 t=change(x,y);
25                 if(!t)flot=0;
26             }
27             sort(area,area+k,cmp);
28             for(int i=0;i<k;i++){
29                 if(area[i].s>area[temp].e)temp=i,num++;
30             }
31             printf("Case %d: %d\n",l,num);
32     }
33     return 0;
34 }