HDU 4296 Buildings(12年成都网络赛-I题-贪心)_hdu4296_nyist_xiaod的博客-程序员秘密

技术标签: 网络  ◆点点滴滴  【贪心】  

题目链接:Click here~~

题意:

有 n 个地板,每个地板 i 有两个权值 Wi, Si,且 PDV(i) =  (ΣWj) - Si ( j 表示在 i 上面的地板)。问如何调整顺序,使得【max(PDV)】最小。

解题思路:

假设现在有 i、j 两个地板需要安排顺序。

若 i 在上,Pi = -Si,Pj = Wi - Sj。

若 j 在上,Pi' = Wj - Si,Pj' = -Sj。

显然有 Pi <= Pi',那么若 Pj <= Pi',则 max(Pi,Pj) <= Pi' <= max(Pi',Pj')。

即 Wi+Si <= Wj+Sj 时,i 在上更能使结果变小。

由此可推出,n 个地板时,按 Wi+Si 递增的顺序排列,max(PDV) 最小,且由上面的递推式可以看出,max(PDV)一定在最下面那层。

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n,w,s;
    while(~scanf("%d",&n))
    {
        int mmax = 0;
        __int64 sum = 0;
        while(n--)
        {
            scanf("%d%d",&w,&s);
            sum += w;
            mmax = max(mmax,s+w);
        }
        printf("%I64d\n",sum-mmax<0 ? 0 : sum-mmax);
    }
    return 0;
}

Ps:这题的数据随机了那么多竟然没随机出为负数的情况。Orz。


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dgq8211/article/details/7988111

智能推荐

人工智能神经网络bp算法及其数学演算过程_bp神经网络sigmoid_王小王zldenny的博客-程序员秘密

BP 算法这是第一次尝试在csdn上写blog,主要因为我也是刚刚接触人工智能,所以各方面都在尝试中,所以想通过这种方式以讲代学,内有不足之处,希望各路大佬能够多多包涵。预备知识在开始之前,首先需要补充一点预备知识。1. 激活函数sigmoid函数:sigmoid 函数是人工智能神经网络中最常使用的一类激活函数,其数学表达式为:...

win10设置HTML桌面背景,win10系统怎么更换桌面壁纸?windows10更换桌面壁纸的方法..._烧伤科医生陈郑礼的博客-程序员秘密

好看的电脑桌面壁纸,可以让我们在使用电脑时心情更加愉悦。最近,就有一些win10系统用户反映自己觉得win10默认的桌面壁纸很难看,想要把它更换掉,却又不知道该如何操作。接下来,小编就向大家分享windows10系统更换桌面壁纸的方法。具体方法如下:1、我们更新系统以后,win10默认的桌面壁纸是一张蓝色背景的图片,见下图;然后这个背景并不是太美观,所以我们可以更换一张;2、但是很多人找不到系统自...

Android源码bootable解析之bootloader LK(little kernel)_little kernel uboot_ffmxnjm的博客-程序员秘密

http://www.07net01.com/2016/11/1721675.html记得当初学linux时候,bootloader 代码相对来说还比较简单,主要几个汇编文件加上几个C文件,编译一个uboot就ok了。做Android驱动后,发现Android专门做了一个目录bootable来实现boot等相关功能。功能也比较多,所以就准备来研究一下这一部分。今天就先研究一下LK,LK全称

这款优秀的笔记应用,真的让我相见恨晚_殴德Tomatooo的博客-程序员秘密

上面这些工具的确有时非常高效。だが,如果你对现在笔记工具的概念还停留在这些本地编辑器上,那你真的大错特错了。

[MIMO-OFDM通信系统的频谱效率matlab仿真] -- MATLAB仿真MIMO-OFDM通信系统的频谱利用效率_ofdm通信系统matlab_code_kd的博客-程序员秘密

频谱效率是评价通信系统性能的重要指标之一,本文将基于MATLAB进行MIMO-OFDM通信系统的频谱效率仿真。通过上述步骤,我们成功进行了MIMO-OFDM通信系统的频谱效率仿真,并计算得到了频谱效率。首先,我们需要设置通信系统参数:载波数、子载波数、天线数、调制方式等。[MIMO-OFDM通信系统的频谱效率matlab仿真] – MATLAB仿真MIMO-OFDM通信系统的频谱利用效率。最后,我们对接收信号进行解调、去除循环前缀、FFT变换,并计算频谱效率。

启动Docker时,报 Failed to instantiate CLSID_VirtualBox w/ IVirtualBox, but CLSID_VirtualBox w/ IUnknown_我是范特西啊的博客-程序员秘密

在使用DockerToolbox安装完docker后,启动报错,错误信息如下: Failed to instantiate CLSID_VirtualBox w/ IVirtualBox, but CLSID_VirtualBox w/ IUnknown 报错信息如图: 我的系统是WINDOWS 7 64位解决办法是:修改注册表1、 win+r 快捷键打开 “运行”,输入regedit 打

随便推点

光纤LP模式分解_Valerius_zhaohui的博客-程序员秘密

光纤LP模式分解10个模式合成后的理想分布图和重建分布图以及残差图df = pd.DataFrame()# 设置谱图cm=plt.cm.get_cmap('Spectral_r')# 创建画布fig = plt.figure(figsize=(27, 9))# 设置样例个数case_nums = 9# 设置行文字解释group_name = ["Measurement", "Reconstructed", "Residual"]for i in range(case_nums):

ImageNet Classification with Deep Convolutional Neural Networks_Alanyannick的博客-程序员秘密

ImageNet Classification with Deep Convolutional Neural NetworksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton摘要我们训练了一个大型的深度卷积神经网络,来将在ImageNet LSVRC-2010大赛中的120万张高清图像分为1000个不同的类别。对测试数据

springboot2.x整合react部署到nginx完美结合_sping boot 和dist怎么通过nginx交互_希尤的博客-程序员秘密

文章目录1. 思路1.1 springboot微服务相关1.2 前端react、VUE相关打包部署1.3 前端怎么整合后端?用nginx1. 思路1.1 springboot微服务相关比如我sprinboot总共有3个微服务ABC ,A:A服务负责和前端交互,端口为8080B: A服务所生产的发邮件、信息等都是去访问B服务,这个时候A跨服务调用B,B的端口是8081C:A服务接口的...

(原创)产生AM调幅信号的DDS——VHDL_vhdl实现dds_qdk0901的博客-程序员秘密

 library ieee;use ieee.std_logic_1164.all;use IEEE.numeric_std.all;USE IEEE.std_logic_unsigned.ALL;use ieee.std_logic_arith.all;-- -----------------------------------------------Entity amdds_module is

Snapshot和Release版本_snapshot release_code_agent的博客-程序员秘密

Snapshot和Release版本1.snapshot版本自动获取服务器最新代码原理我们在提交snapshot版本时 mvn deploy,会提交一个带时间搓的版本号!maven会根据模块的版本号(pom文件中的version)中是否带有“-SNAPSHOT”(注意这里必须是全部大写)来判断是快照版本还是正式版本。如果是快照版本,那么在mvn deploy时会自动发布到私服的快照版本库中;如果是正式发布版本,那么在mvn deploy时会自动发布到正式版本库中。我们下载依赖到本地仓库时,也会带