#Doing home work again
Title Link: Click here~~
Title:
There are n assignments, and each assignment has its own deadline. When the deadline is exceeded and the assignment has not been completed, the corresponding score will be deducted. Ask how you can minimize points.
Solution 1:
n-door assignments are sorted by score from large to small, and then each assignment is arranged on the day closest to its deadline (first arranged on the deadline day, if there is already arrangement on that day, look for the day ahead), and this day is marked as used, if not, points will be deducted.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
bool vis[1000];
#define fre freopen("C:\\Users\\Dell\\Desktop\\in.txt", "r", stdin);
struct node{
int dead;
int sub;
bool operator < (const node &a)const{
return a.sub<sub;
}
}stu[1005];
int main(){
//fre;
int t, n, totsub;
cin >> t;
while (t--){
vis[0] = 1;
totsub = 0;
cin >> n;
for (int i = 0; i<n; i++)cin >> stu[i].dead;
for (int i = 0; i<n; i++)cin >> stu[i].sub, totsub += stu[i].sub;
sort(stu, stu + n);
for (int i = 0; i<n; i++){
//int k = 0;
for (int j = stu[i].dead; j >= 1; j--){
if (vis[j] == 0){ vis[j] = 1; totsub -= stu[i].sub; break; }
}
}
cout << totsub << endl;
memset(vis, 0,sizeof(vis) );
}
return 0;
}
Solution 2:
Sort the dates from small to large first. If the dates are the same, the ones with more points will be in the front. If there are more points deducted on the same date, use the previous time to do the work with less points deducted; if there are no smaller ones, deduct the points of the work. On, which is much better than the previous algorithm.
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<queue>
#include <bits\stdc++.h>
using namespace std;
#define fre freopen("C:\\Users\\Dell\\Desktop\\in.txt", "r", stdin);
priority_queue<int, vector<int>, greater<int> >q; //Small first out queue
struct in
{
int d, s;//deadline，score
}c[1010];
bool cmp(in a, in b){
return a.d<b.d;
}
int main()
{
fre;
int T, n, i, j, t, cnt, ans;
scanf("%d", &T);
while (T--){
cnt = ans = 0;
t = 1;
while (!q.empty()) q.pop();
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &c[i].d);
for (i = 1; i <= n; i++) scanf("%d", &c[i].s);
sort(c + 1, c + n + 1, cmp);
for (i = 1; i <= n; i++){
//Put it into the queue sorted from small to large, and when there is no time to do the job with large score later, discard the job with small score from the team head (the job with small score).
q.push(c[i].s);
//If the deadline is the same, i.e. there is more than one course to be handed in on a certain day, you must choose one of them to give up, and choose the one with the lowest cost, but it is not open
//Decide which door to do that day
if (c[i].d>=t) t++;
else {
ans += q.top(); q.pop();
}
}
printf("%d\n", ans);
}
return 0;
}