赶作业 C++

赶作业 C++

题目描述

小墨老师总是不及时做作业，所以他总有很多的作业要做。每个老师都给了他一个完成作业的最后期限，如果他超过期限交作业，老师就会在他的期末评价中扣分。假设做每一门作业总是要一天。小墨老师希望你能够帮助他安排做作业的一个顺序，以便能够被扣掉的分数最少。

输入格式:

输入包含了多个测试用例。输入的第一行是一个整数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

这道题是用结构体的方式解决的，缕一缕思路，其实就是将所有作业截至日期和损失分数进行排序，第一关键字是截止日期升序，第二关键字是损失分数降序，然后进行循环，如果当前作业的截至天数小于今天的日期则已经过了该天，则损失分数加上去就可以，然后就是往后找截止日期还没到的作业先做了，并标记t=0代表这个作业已经做了，及时止损，接下来查询的时候遇到t=0情况日期不加，直接跳过

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
using namespace std;
struct work{int day;int lose;int t=1;
};
struct work homework[1000];
bool cmp1(struct work a1,struct work a2){if(a1.day==a2.day){return a1.lose>a2.lose;}return a1.day<a2.day;		
}
main()
{int n,m;cin>>n;while(n--){cin>>m;for(int i=0;i<m;i++){cin>>homework[i].day;}for(int i=0;i<m;i++){cin>>homework[i].lose;homework[i].t=1;}struct work a;sort(homework,homework+m,cmp1);int ans=0,day=1;for(int i=0;i<m;i++){if(homework[i].day<day && homework[i].t==1){ans+=homework[i].lose;for(int j=i+1;j<m;j++){if(homework[j].day>=day&&homework[j].t==1){homework[j].t=0;break;}}}if(homework[i].t==1){day++;}}cout<<ans<<endl;}
}