1799Doing Homework again--贪心算法

Doing Homework again

Time Limit:1000MS Memory Limit:32768K
Total Submit:61 Accepted:23

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。如果在指定的日期内完成则不会扣分，且每个作业只需要一天完成，那么肯定会想到先把学分多的先做，是不是这样就能行呢,先看一组例子吧：

1 4 6 4 2 4 3
3 2 1 7 6 5 4
如果只考虑学分多的先做那么排列就会是：7654321 ，但这并不是最优的安排。

2。换个角度想了想，要使扣分少，我应该尽量使扣分少的过期在做，最好要让学分多的在它指定的那天完成，这样就会使得这天被扣分数尽量少。
结果思路就出来了： 1。先处理分数多的作业，把分数多的安排在它最后期限那一天。
2。如果那天被占用了，就往前一天安排。
3。如果前面没有日期了，就安排最后那天处理这个作业。此时就要扣掉对应的学分。

算法设计：1。利用STL中的sort()进行排序，但是因为定义了一个数据结构，需要重新写个判断函数。
2。定义一个vist[]数组来标记该天是否被安排



#include
void f(int a[],int b[],int n)
{
int i,k,j,t;
for (i=0;i{
k=i;
for (j=i+1;jif (b[j]>b[k])
k=j;
if (i!=k)
{
t=a[k];
a[k]=a[i];
a[i]=t;
t=b[k];
b[k]=b[i];
b[i]=t;
}
}
}
int main()
{
int i,j,n,k,s,m,max,a[1001],b[1001],p[1001];
scanf("%d",&m);
while (m)
{
scanf("%d",&n);
max=a[0];
for (k=

0;k{
scanf("%d",&a[k]);
if (a[k]>max)
max=a[k];
}
for (k=0;k<=n;k++)
p[k]=0;
s=0;
for (k=0;kscanf("%d",&b[k]);
f(a,b,n);
for (i=0;i{ j=a[i];
while(1)
{
if(j<1)
{
s=s+b[i];
break;
}
if(p[j]==0)
{
p[j]=1;
break;
}
else
j--;
}
}
printf("%d\n",s);
m--;
}
return 0;
}