Week4 作业 A

题目描述：

ZJM 有 n 个作业，每个作业都有自己的 DDL，如果 ZJM 没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。

所以 ZJM 想知道如何安排做作业的顺序，才能尽可能少扣一点分。

请你帮帮他吧！(1<=N<=1000)

思路：

O(n^2)算法即可；很显然，扣分越多的越早做越好；所以，按扣分的大小降序排列，对第i个作业，其ddl为ddl_i，在ddl_i前，如果有空闲，就安排，没有就扣分，依次进行；

注意，一定要最接近ddl_i做才最好，因为这样对前面的作业影响最小。

正确性证明：

假设第i个作业的ddl是ddl_i，分配给这个作业的时间是 ddl_i - k ，则说明从 ddl_i - k + 1 到 ddl_i 都已经安排了任务，则以ddl_i - k 为真·ddl 的作业中，做扣分最大的一定是最划算的，依次类推至i=n

代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm> 
 4 #include <cstring>
 5 using namespace std;
 6 const int MAXN = 1e3+5;
 7 struct homework
 8 {
 9     int ddl;
10     int num;
11     bool operator<(const homework &x) const
12     {
13         if(x.num!=num) return num>x.num;    //扣分多的应该最先写 
14         else return ddl<x.ddl;   
15     }
16 }a[MAXN];
17 int time[MAXN];
18 int main()
19 {
20     //freopen("a.in","r",stdin);
21     int T; cin>>T;
22     while(T--)
23     {
24         memset(time,0,sizeof(time));
25         int n; cin>>n;
26         for(int i=0;i<n;i++)
27             scanf("%d",&a[i].ddl);
28         for(int i=0;i<n;i++)
29             scanf("%d",&a[i].num);
30         sort(a,a+n);
31         int ans=0;
32         for(int i=0;i<n;i++)
33         {
34             int j;
35             for(j=a[i].ddl;j>=1;j--)
36                 if(time[j]==0) { time[j]=-1;break; }
37              
38             if(j==0) ans+=a[i].num;
39         }
40         cout<<ans<<endl;
41     }
42     
43 }

心得：

1、对于多组数据，建议用变量大写字母T，而不是小写字母t，因为常常会用小t在内部，编译出错却找不到原因。

2、多组数据，数组/容器/while循环外定义的变量，有些需要clear()/memset/置零，否则出现奇怪的问题找不到原因。