HDU-1789_sdnuzsj的博客-程序员秘密

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test. And now we assume that doing everyone homework always takes one day. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
InputThe input contains several test cases. The first line of the input is a single integer T that is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=1000) which indicate the number of homework.. Then 2 lines follow. The first line contains N integers that indicate the deadlines of the subjects, and the next line contains N integers that indicate the reduced scores.
OutputFor each test case, you should output the smallest total reduced score, one line per test case.
Sample Input
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
Sample Output
0
3
5
题意:ACM大佬比赛回来但无奈作业都没写完,现在给你他的每门课程的deadline和如果不写完所扣的分数。现在要求你这样安排才能使扣分最少。输出最少的分数。
思路:贪心算法。先把分数按从大到小排序,然后将最大的放在它的最后的期限做。依次来如果deadline有作业可做,就往前进一个直到第一天为止。
AC代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct homework
{
    int dl;
    int score;
    bool flge;
} hw[1005];

bool vis[1005];

bool cmp(homework a,homework b)
{
    return a.score>b.score;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&hw[i].dl);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&hw[i].score);
        }
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            hw[i].flge=0;
        }
        sort(hw,hw+n,cmp);
        for(int i=0;i<n;i++)
        {
            for(int j=hw[i].dl;j>0;j--)
            {
                if(vis[j]==0)
                {
                    vis[j]=1;
                    hw[i].flge=1;
                    break;
                }
            }
        }
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(hw[i].flge==0)
            {
                sum+=hw[i].score;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sdnuzsj/article/details/60578901

智能推荐

黑马程序员——Map_Camwly的博客-程序员秘密

------Java培训、Android培训、iOS培训、.Net培训、期待与您交流! -------   Map属于一种映射关系的集合。 Map集合里存在两组值,一组是key,一组是value。Map里的key不允许重复。通过key总能找到唯一的value与之对应。这个关系就好比如说,一栋楼,她的房号是不可以重复的,但是里面的布置可以一样。  如下是Map中的几个重要方法:

微服务用 Spring Cloud 多还是 Dubbo 多?_Java后端技术的博客-程序员秘密

往期热门文章:1、《往期精选优秀博文都在这里了!》2、真香!IDEA 最新版本,支持免打扰和轻量模式!3、微服务如何防止雪崩?阿里开源之Sentinel限流、熔断来帮你!4、为什么很多S...

UVA 1658 Admiral (费用流+拆点)_明日可7的博客-程序员秘密

分析:把每个点分为 n 和 n'  ,两点之间连一条容量为1,费用为0的边,这样就能保证一个点只能被经过一次。#include &amp;lt;iostream&amp;gt;#include &amp;lt;cstdio&amp;gt;#include &amp;lt;cstring&amp;gt;#include &amp;lt;cmath&amp;gt;#include &amp;lt;algorithm&amp;gt;#include &amp;lt;map&amp;...

成为项目经理需要哪些条件或证书?_lhlyy77的博客-程序员秘密_项目经理证书报考条件

1.人员开发能力1.项目经理应创造一种学习环境,使员工能从他们所从事的工作中,从他们所经历或观察的情景中得到知识。如尽可能给成员分配全面的任务,使他们丰富知识。如一个没用过Excel的人去用Excel处理数据,这就能使他学会使用Excel。或是让一个阅历不足的成员能跟经验丰富的成员一起工作,使新的成员从经验丰富的人那里学到更多的东西。2.让他们参加正式的培训课程。2.领导能力1.项目经理需要采取民主式的领导方式对于项目经理而言,采用这种领导方式比主要依靠职权的独裁式或命令式的管理方式更为

Axure RP使用攻略--带遮罩层的弹出框(9)_汐若雨的博客-程序员秘密_axure点击弹出浮层

实现目标:1、&nbsp;&nbsp; 点击按钮弹出带遮罩层的对话框;2、&nbsp;&nbsp; 页面上下左右滚动时,弹出的对话框水平和垂直始终居中。实现步骤如下:1、 拖入编辑区2个矩形,并点右键—转换—转换为动态面板;2、 双击其中一个动态面板设置标签为“遮罩层”(看个人喜好随便命名),并双击状态1进入编辑;3、 点击状态1里面的矩形,设置大小与网站页面大小相同,以便完全遮盖;然后,设置矩形边框为“无”;最后设置填充色的透明度为50%(看个人喜好),并选择填充色为灰色(看个人喜好);.

cocos2dx之创建Button_漫步者、的博客-程序员秘密_cocos2dx 创建button

利用CCControlButton创建一个Button,代码如下:void MyBottonBastLayer::initLayer() { CCSize size = CCDirector::sharedDirector()->getWinSize(); CCScale9Sprite *psc9Selected = CCScale9Sprite::create("btn-ab

随便推点

2019年上半年程序员考试第六题目,解析_dongxinddd123的博客-程序员秘密

题目大意: 现如今线下支付可以用现金(Cash)、移动支付、银行卡(Card)(信用卡(Creditcard)和储蓄卡(DebitCard))等多种支付方式(PaymentMethod)对物品(Item)账单(Bill)进行支付。 下图是某系统的列类图解析代码:#include&lt;iostream&gt;#include&lt;vector&gt;#include&...

21年最新-李沐-动手学深度学习第二版_lqfarmer的博客-程序员秘密_动手学深度学习第二版

阿斯顿·张、李沐联合编写的,面向中文读者的能运行、可讨论的深度学习教科书《动手学深度学习》又更新了。 bshq:21年最新-李沐《动手学深度学习第二版》中、英文版免费分享 【关注第二版更新】英文版前八章已翻译至中文版第二版,并含多种深度学习框架的实现。英文版还新增了注意力机制、BERT、自然语言推理、推荐系统和深度学习的数学等。如果想及时获取最新修订或增添的信息, 请关注本书的中文开源项目和英文开源项目。 【购买第一版纸质书(上架4周重印2次...

asp毕业设计—— 基于asp+access的期刊稿件处理系统设计与实现(毕业论文+程序源码)——期刊稿件处理系统_毕业设计方案专家的博客-程序员秘密

1.本课题主要就互联网中的网站建立展开研究,通过对asp语言和数据库等技术的学习,设计出基于Web的期刊系统。该系统设置了三级用户,每级用户拥有对系统操作的不同权限,此权限由系统管理员即admin级别用户来管理。用户登录后进行在线投稿,查询稿件状态,包括评审费查询,版面费查询,收录查询等。评审专家登录后进行稿件评阅等。期刊管理员登录管理期刊文章,管理评审专家列表,分发新投稿给评审专家,处理收稿信息,收评审费信息,评审结果信息,收版面费信息等。2.本文主要内容主要包括如下内容。提示......

android studio容易出现的问题_fjnu_se的博客-程序员秘密

**android studio容易出现的问题**​作为一名android studio的初学者,使用android studio的时候出现了诸多问题,最终多方面查询相关资料后得以解决,其中几个主要的问题。一、sdk路径的问题,因为是很久之前的问题了,没有保留出现问题时的截图,但是解决方法还记得。首先先试试重启电脑,有时候就是加载出错导致的,重启有时候就能解决问题,原本能运行的,有时候就会不能运行。我在尝试多种方法无法修复的时候最终发现只是我加载出错了,重启就可以了,但是在过程中了解了许多处

[CPU+目标检测] openvino实现Robomaster自瞄_三丰杂货铺的博客-程序员秘密_robomaster自动瞄准

这篇文章为大连理工大学Robomaster凌Bug战队的李乐恒同学成果!他在CPU上利用openvino这样的深度学习算法实现了Robomaster的自瞄,大大提高了robomaster自瞄的上界,且达到了良好的检测效果。所有代码全部开源, github主页如下:https://github.com/Len-Li/openvino-robomaster文章目录0.introduction1.1 使用的模型库1.2 数据集1.3 训练+评测1.3.1 安装TensorFlow Object Detec

接口隔离原则详解--七大面向对象设计原则(4)_Geek.Fan的博客-程序员秘密

接口隔离原则的来源:  类A通过接口I依赖类B,类C通过接口I依赖类D,如果接口I对于类A和类B来说不是最小接口,则类B和类D必须去实现他们不需要的方法。因为使用多个专门的接口比使用单一的总接口要好,所以便提出了接口隔离原则。接口隔离原则的目的:  将臃肿的接口I拆分为独立的几个接口,类A和类C分别与他们需要的接口建立依赖关系。也就是采用接口隔离原则。接口隔离原则的两种定义

推荐文章

热门文章

相关标签