ACM | Doing Homework again

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. Ignatius 刚刚从第 30 届 ACM/ICPC 回到学校。 现在他有很多作业要做。 每个老师都给他规定了交作业的截止日期。 如果 Ignatius 在截止日期后交作业，老师将降低他期末考试的分数。 现在我们假设做每个人的作业总是需要一天的时间。 所以 Ignatius 希望你帮他安排一下做作业的顺序，尽量减少分数的降低。

输入格式:

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. 输入包含多个测试用例。 输入的第一行是一个整数 T，它是测试用例的数量。 T 测试用例如下。 每个测试用例都以正整数 N(1<=N<=1000) 开头，表示作业的数量。然后是 2 行。 第一行包含 N 个整数，表示科目的截止日期，下一行包含 N 个整数，表示减少的分数。

输出格式:

For each test case, you should output the smallest total reduced score, one line per test case. 对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。

输入样例:

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

输出样例:

0
3
5

解题思路：

因为要使扣的分数最小，所以需要使延时提交的作业数最少。所以要优先完成时间早的作业。所以我先进行一个排序算法，将所有的作业按照deadline从小到大排序。

void sort(struct homework *homework,int N){
    for(int i=0;i<N;i++){
        for(int j=0;j<N-i-1;j++){
            if((homework+j)->deadline>(homework+j+1)->deadline){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }else if((homework+j)->deadline=(homework+j+1)->deadline && (homework+j)->score<(homework+j+1)->score){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }
        }
    }
}

当然，完全按照deadline也是错误的，例如：

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

完成排序后变成了：

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

此时严格按照deadline排序输出结果是错误的。我们发现如果我们第一天不完成第一个作业，扣的分数反而会更小。所以前面的想法其实不完全正确。

我们需要的是扣的分数最小，所以我们可以优先考虑分数。

那我们先对分数进行排序，如下所示：

void sort(struct homework *homework,int N){
    for(int i=0;i<N;i++){
        for(int j=0;j<N-i-1;j++){
            if((homework+j)->score<(homework+j+1)->score){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }else if((homework+j)->deadline<(homework+j+1)->deadline && (homework+j)->score==(homework+j+1)->score){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }
        }
    }
}

进行如上排序后我们会获得下面的结果：

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

然后我们根据score的权重，把作业“放入”我们需要完成的日子。

当遇到分数相同的，根据日期，我在前面排列时把日期大的放在了待处理队列中相同分数的靠前位置，所以会优先处理。如果在处理时发现该日期已经被占用，那么顺应往前面未被占用的日期处移动，这样能保证该作业能一定能完成。

下面是分步结果：（前面的一列0是用于占位，可以忽略）

0 1 3 3 4 0 
0 6 5 2 7 0 

0 1 2 3 4 0 
0 6 6 2 7 0 

0 1 2 4 4 0 
0 6 6 5 7 0 

0 3 2 4 4 0 
0 4 6 5 7 0 

0 3 2 4 4 0 
0 4 6 5 7 0 

0 3 2 4 4 0 
0 4 6 5 7 0 

0 3 2 4 4 6 
0 4 6 5 7 1 

然后剩余的未完成的作业加起来的分数就是最小的会被扣掉的分数。

源码实现：

#include<stdio.h>
struct homework{
    int deadline;
    int score;
    int availible;
};
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}
void sort(struct homework *homework,int N){
    for(int i=0;i<N;i++){
        for(int j=0;j<N-i-1;j++){
            if((homework+j)->score<(homework+j+1)->score){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }else if((homework+j)->deadline<(homework+j+1)->deadline && (homework+j)->score==(homework+j+1)->score){
                swap(&(homework+j)->score,&(homework+j+1)->score);
                swap(&(homework+j)->deadline,&(homework+j+1)->deadline);
            }
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int N;
        scanf("%d",&N);
        struct homework homework[1001];
        int max_date=0;
        int reduced_score=0;
        for(int i=0;i<N;i++){
            scanf("%d",&homework[i].deadline);
            if(homework[i].deadline>max_date){
                max_date=homework[i].deadline;  //找最大的日期
            }
        }
        for(int i=0;i<N;i++){
            scanf("%d",&homework[i].score);
            reduced_score+=homework[i].score;
        }
        sort(homework,N);
        struct homework schedule[1001];
        for(int i=0;i<=max_date;i++){
            schedule[i].availible=0; //1表示占用
        }
        for(int i=0;i<N;i++){
            if(schedule[homework[i].deadline].availible==0){
                schedule[homework[i].deadline].deadline=homework[i].deadline;
                schedule[homework[i].deadline].score=homework[i].score;
                reduced_score-=homework[i].score;
                schedule[homework[i].deadline].availible=1;
            }else{
                for(int j=homework[i].deadline;j>=1;j--){
                    if(schedule[j].availible==0){
                        schedule[j].deadline=homework[i].deadline;
                        schedule[j].score=homework[i].score;
                        reduced_score-=homework[i].score;
                        schedule[j].availible=1;
                        break;
                    }
                }
            }
        }
        printf("%d\n",reduced_score);
    }
    return 0;
}