首页 > 代码库 > hdu 1789 doing homework again

hdu 1789 doing homework again

2024-07-16 14:08:41   214人阅读

这题的意思大概是 每个老师都会给出交作业的期限和没按时交会扣掉的分数 要求出扣除最少分数的情况
是一题典型的贪心
一开始只是把排序排完 发现不大对就无解了 看了题解才发现排序后还要合理安排 思维还不够到位啊
排序把扣除分数最大的排在最前面
如果满足条件就把第 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|1using 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;}

　　


联系
我们