【贪心】赶作业
<center>
提交: 18 解决: 12
[提交][状态][讨论版] </center>
问题 : 【贪心】赶作业
时间限制: 1 Sec 内存限制: 64 MB提交: 18 解决: 12
[提交][状态][讨论版] </center>
题目描述
小墨老师总是不及时做作业，所以他总有很多的作业要做。每个老师都给了他一个完成作业的最后期限，如果他超过期限交作业，老师就会在他的期末评价中扣分。假设做每一门作业总是要一天。小墨老师希望你能够帮助他安排做作业的一个顺序，以便能够被扣掉的分数最少。
输入
输入包含了多个测试用例。输入的第一行是一个整数T，代表测试用例的个数。接下来的就是T个测试用例的输入。每个测试用例都从一个正整数N(1≤N≤1000)开始，代表了作业的数目。接下来有2行。第一行包含N个整数，分别代表各个作业提交的最后期限；第二行也有N个整数，即对应于各个作业操过时间提交的扣分。
输出
对每一个测试用例，应该在一行中输出最小的扣分数。
样例输入
2
3
3 3 3
10 5 1
3
1 3 1
6 2 3
样例输出
0
3
解题思路：题目要求输出扣最少的分数，看的第一眼感觉非常简单，于是先按照所给的期限升序排序，然后顺着看，当所给期限早于分配到的期限时就记上这一个。结果提交不对。
然后又按照分数降序排序，再顺着看所给期限与分配到的位置，结果提交仍然不对。
最后恍然大悟，应该是自己给它分配时间，首先所扣分数按照降序排列，然后取第一个，从他所给期限的最晚时间开始安排，如果这一天已经有安排，安排到前一天。。。这样先让扣分最多的有着落，最后剩下扣分少的，才是扣最少分的正确策略。
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; struct node{ int date; int score; int sd; }; node subject[1005]; int cmp(node a,node b){ //return a.date<b.date||a.date==b.date&&a.score>b.score; return a.score>b.score||a.score==b.score&&a.date<b.date; //return a.sd>b.sd; } int main() { int t; int n; int s=0; int b[1005]={0}; scanf("%d",&t); for(int j=0;j<t;j++){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&subject[i].date); } for(int i=1;i<=n;i++){ scanf("%d",&subject[i].score); subject[i].sd=0; } sort(subject+1,subject+n+1,cmp); for(int i=1;i<=n;i++){ for(int ii=subject[i].date;ii>0;ii--){ if(b[ii]==0){ b[ii]=1; subject[i].sd=1; break; } } if(subject[i].sd==0){ s+=subject[i].score; } } printf("%d\n",s); s=0; memset(b,0,sizeof(b)); } return 0; }
查看16道真题和解析
