题意:
已知有n个作业,每个作业呢,都是一天可以做完,每个作业都有一个截止日期,每个作业如果超过他的截止日期会扣分,最后让你求一个怎么安排求得一个最小扣的分数。 比如现在有3个作业 截止日期:3 3 3 超过扣分:1 5 4 我们看到他们的截止日期都是3天,所以每天做一份。3天刚好做完,扣0分。 思路: 一开始一直一直瞎搞,因为听说这道题目吧。。记忆中是贪心。然后就瞎几把排序各种,按时间排,感觉非常像DP。。。但是好难DP。。然后还是贪心吧。按照花费从大到小排序,然后能处理就处理,不能处理就只能不处理了(sum+=q[ i ].t)。#includeusing namespace std;typedef long long LL;typedef unsigned long long ULL;const double eps=1e-5;const double pi=acos(-1.0);const int mod=1e9+7;const int INF=0x3f3f3f3f;const int N=1e3+10;struct asd{ int d; int t;};asd q[N];bool vis[N];bool cmp(asd x,asd y){ if(x.t>y.t) return 1; else if(x.t==y.t){ if(x.d >t; while(t--) { int n,i,sum,j; cin>>n; for(i=1;i<=n;i++){ scanf("%d",&q[i].d); } for(i=1;i<=n;i++){ scanf("%d",&q[i].t); } sort(q+1,q+n+1,cmp); memset(vis,0,sizeof(vis)); sum=0; for(i=1;i<=n;i++){ for(j=q[i].d;j>=1;j--){ if(!vis[j]){ vis[j]=1; break; } } if(j==0) sum+=q[i].t; } cout< <