解题报告 HDU1789 Doing Homework again

Doing Homework again

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

10 5 1

1 3 1

6 2 3

1 4 6 4 2 4 3

3 2 1 7 6 5 4

Sample Output

题意：

　　给出课程的deadline和超时所扣的分做一个作业要一天求出最少的扣分方案

错误思路：

　　一开始想当然地先对deadline按升序排序再对相同deadline的按扣分多少按降序排序

　　然后从头开始当之后的数据deadline比已用天数小的时候就+到sum里

　　这个思路是不对的我们从最后一组数据就能测试出他的问题如果按这种思路

　　排序后：1 2 3 4 4 4 6

　　　　　　3 6 4 7 5 2 1

　　那么我们做到第四个数据之后的数据就全部都无法完成了得出的结果是8

　　但是这个case下的最优解其实是：不做第一天的3和第四天的2 其他都可以完成结果是5

正确思路：

　　这里我用的是hash表的思路

　　先按分数降序排列然后从头开始加到时间表里

　　表的4 放上数据7 意思是第四天完成7这个作业

　　放5的时候冲突了于是放到3 第三天完成5这个作业

　　之后同理如果无法放到表中说明这个任务无法完成加到sum里

ac代码：

其中的判定value大小的地方有垃圾部分因为已经按降序排列所以插入的时候没有比其中数据小的情况懒得删了

 1 #include <iostream>
 2 using namespace std;
 3 int work;
 4 int sum=0;
 5 struct w
 6 {
 7     int dl;
 8     int score;
 9 }a[1005];
10 
11 void sort(w *a)
12 {
13     for(int i=0;i<work-1;i++)
14     {
15         for(int j=i+1;j<work;j++)
16             if(a[j].score>a[i].score)
17             {
18                 w t=a[j];
19                 a[j]=a[i];
20                 a[i]=t;
21             }
22     }
23 }
24 void insert(int *timeset,int pos,int value)
25 {
26     if(timeset[pos]==0)
27         timeset[pos]=value;
28     else if(timeset[pos]>value&&(pos-1)>0)
29         insert(timeset,pos-1,value);
30     else if(timeset[pos]>value&&(pos-1)<=0)
31         sum+=value;
32     else if(timeset[pos]<=value)
33     {
34         int t=timeset[pos];
35         timeset[pos]=value;
36         if((pos-1)>0)
37             insert(timeset,pos-1,t);
38         else
39             sum+=t;
40     }    
41 }
42 int main()
43 {
44     int N;
45     cin>>N;
46     for(int n=1;n<=N;n++)
47     {
48         sum=0; 
49         cin>>work;
50         int maxdl=0;
51         for(int i=0;i<work;i++)
52         {
53             cin>>a[i].dl;
54             if(maxdl<a[i].dl)
55                 maxdl=a[i].dl;
56         }
57         for(int i=0;i<work;i++)
58             cin>>a[i].score;
59         int *timeset=new int[maxdl+1];
60         for(int i=0;i<maxdl+1;i++)
61             timeset[i]=0;
62             
63         sort(a);
64         
65         for(int i=0;i<work;i++)
66             insert(timeset,a[i].dl,a[i].score);
67 
68         cout<<sum<<endl;    
69     }
70     return 0;
71 }