题目链接: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。
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
算法-确定比赛名次(HDU-1285).rar
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
HDU 1010-2500解题报告,ACMer可以借鉴一下
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
hdu2000-2014ac代码,虽然只有几道,但都是简单的
杭电ACM课件2014版之 (HDUACM201403版_03)贪心算法
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法