这题的意思大概是 每个老师都会给出交作业的期限和没按时交会扣掉的分数 要求出扣除最少分数的情况
是一题典型的贪心
一开始只是把排序排完 发现不大对就无解了 看了题解才发现排序后还要合理安排 思维还不够到位啊
排序把扣除分数最大的排在最前面
如果满足条件就把第 i 门作业安排在截至日期那天 否则则前推
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define MAXN 1000
#define INF 0x7ffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
struct work
{
int dead,score;
};
work num[1200];
int vis[1200];
int cmp(work a,work b)
{
if(a.score!=b.score)
return a.score>b.score;
else
return a.dead>b.dead;
}
int main()
{
int t,n,i,j;
cin>>t;
while(t--)
{
mem(num,0);
mem(vis,0);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&num[i].dead);
}
for(i=1;i<=n;i++)
{
scanf("%d",&num[i].score);
}
sort(num+1,num+n+1,cmp);
int sum=0,day=1;
for(i=1;i<=n;i++)//第 i 个
{
for(j=num[i].dead;j>=1;j--)
{
if(!vis[j]) {vis[j]=1;break;}
}
if(j==0) sum+=num[i].score;
}
printf("%d\n",sum);
}
return 0;
}
hdu 1789 doing homework again,布布扣,bubuko.com
原文：http://www.cnblogs.com/sola1994/p/3900408.html