Doing Homework again
Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4294Accepted Submission(s): 2505
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
#include <stdio.h>
#include <stdlib.h>
int t, n, i, j, k;
typedef struct Node {
int time, val;
}Node;
int cmp(const void * a, const void * b){
Node * aa = (Node *)a;
Node * bb = (Node *)b;
if(bb->val - aa->val == 0)
return aa->time - bb->time;
return bb->val - aa->val;
}
struct Node nodes[1001];
int opt[1001];
int main(void) {
scanf("%d", &t);
while (t--) {
int max = 0,sum=0;
scanf("%d", &n);
for (i = 0; i < n; i++){
scanf("%d", &nodes[i].time);
if(max < nodes[i].time)
max = nodes[i].time;
};
for (i = 0; i < n; i++){
scanf("%d", &nodes[i].val);
sum += nodes[i].val;
}
for(i=0; i<=max; i++)
opt[i] = 0;
qsort(nodes, n, sizeof(Node) ,cmp); //按学分排序
int ans =0;
for(i=0; i<n; i++){ //优先大学分。同时,大学分的能往后拖延则拖延
int k = nodes[i].time;
while(opt[k] && k>0){
k--;
}
if(k != 0){ //表明该课程可以完成
opt[k] = nodes[i].val;
ans += opt[k];
}
}
printf("%d\n",sum-ans);
}
return 0;
}
分享到:
相关推荐
java-贪心算法-物流派件用车最少
算法基础 第6章 贪心算法--第5版(2022.03.05).pdf
贪心算法--数据结构与算法必知必会,希望对在学数据结构与算法的你能有所帮助
5.贪心算法贪心算法-计算机编程 数据结构
贪心算法-最小平铺路径,简单讲解贪心算法。贪心算法、算法导论、算法、c语言。 贪心算法-最小平铺路径,简单讲解贪心算法。贪心算法、算法导论、算法、c语言。
C#贪心算法 C#贪心算法-找钱问题源码 贪心算法
C++贪心算法-部分背包问题
贪心算法-背包装载问题
算法基础 第6章 贪心算法--第5版(2021.01.26).pdf
第8章贪心算法-Huffman算法,java考试参考资料,大家踊跃下载。
第4章-贪心算法-复习.ppt
顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有...
本算法比较清晰,易读。运行后自动出结果。 背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优...
多机调度问题贪心算法-06-元素溢出.ev4.rar
《信息学奥赛一本通》:第6章 贪心算法--第5版
贪心算法-旅行规划问题.doc
多机调度问题贪心算法-04-常用布局样式属性.ev4.rar
用C语言编写的贪心算法,源代码,不需改动,就可以运行,绝对无误。
多机调度问题贪心算法-05-常用文本的样式属性.ev4.rar
主要是使用贪心算法,实现活动安排的个数最多