文档章节

Codevs 挂缀

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 971
阅读 8
收藏 0
题目描述 Description

“珠缀花蕊,人间几多酸泪”…… 
挂缀在很早就被人们作为一种装饰品,垂坠的风韵,华丽摇曳的摆动,展现出一种与众不同的优雅与高贵。而我们的主人公小Q,正想买一条漂亮的挂缀放在寝室里作为装饰。 
挂坠的构成,是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成:分别是珠子、珠子上方的连接环与珠子下方的挂钩(如下图) 。我们可以简单的认为从上往下数的第 i 个缀珠是将它的连接环套在其上方(也就是第 i-1 个)缀珠的挂钩之上(第一个除外) 。小 Q想买一根足够长的挂缀,这样显得更有韵味☺ 

然而商店的老板告诉小Q,挂缀是不可能做到任意长的,因为每一个珠子都受到重力作用,对其上方的挂钩有一定的拉力,而挂钩的承受能力是有限的。老板还告诉小 Q,他一共拥有 N 个珠缀(假设每一个珠缀都很漂亮,小 Q 都很喜欢) ,每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的,当且仅当对于其上的每一个珠缀,它下方所有珠缀的重量和(不包含自身)不超过其挂钩的承受能力。 
小Q希望她的挂缀尽量长,你能帮她计算出最长可能的稳定挂缀么?当然,如果有多个可选方案,小Q希望总重量最小的。

输入描述 Input Description

 第一行包含一个正整数 N,表示商店拥有的珠缀数目。
接下来 N行,每行两个整数(Ci , Wi),分别表示第i 个珠缀的承受能力与重量。

输出描述 Output Description

包行两行。第一行包含一个整数L,表示可以找到的最长稳定挂缀长度。

第二行包含一个整数 W,表示可以找到的长度为 L 的稳定挂缀中的最小重量和。

样例输入 Sample Input


3 5 
5 1 
3 2 
4 6

样例输出 Sample Output


8

数据范围及提示 Data Size & Hint

对于 30%的数据,N ≤ 10000; 
对于 100%的数据,N ≤ 200000; 
对于所有的数据,Wi, Ci不超过231

看到题目来源CTSC07年国家队选拔赛的时候我几乎是崩溃的。。然后看了眼数据范围。。继续崩溃。。。

这道题是一道特别特别特别经典的贪心。。为什么说是贪心呢?因为我只需要升序排列,看当前挂缀的承重能否负担得起当前重量。这样我们在O(n)的时间内得到了一个长序列,并且我们可以证明的是  最后的答案一定是这个长序列其中的子序列。

那么从上往下for,如果当前挂缀的重量小于我现在的挂缀承重,那么添加进去。如果存在一个挂缀的承重大于某一个并且重量<=这一个,那么替换这个挂缀。既然可以这样贪心,那么我们可以用堆来进行维护,相应的操作就是pop和push。

下面是代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct hq{
    long long wgt,f,sum;
    bool operator <(hq const &a) const
      {return sum<a.sum;}
}a[1000001];
int n;
long long nowwgt=0,nowl=0;
priority_queue<int> q;
int main()
{
    int i;
    scanf("%d",&n);
    for (i=1;i<=n;++i)
      {
        scanf("%I64d%I64d",&a[i].f,&a[i].wgt);
        a[i].sum=a[i].f+a[i].wgt;
      }
    sort(a+1,a+n+1);
    for (i=1;i<=n;++i)
      {
        if (nowwgt<=a[i].f) {q.push(a[i].wgt); nowl++; nowwgt=nowwgt+a[i].wgt;}
        else if (q.top()>a[i].wgt) {nowwgt=nowwgt-q.top()+a[i].wgt; q.pop(); q.push(a[i].wgt);}
      }
    printf("%lld\n%lld\n",nowl,nowwgt);
}


本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49582535

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
nginx location 配置中 try_files, alias, root, index 的

需求场景 朋友让我帮忙挂一个网页,有点类似“钓鱼”的性质(开玩笑,没这么严重),就是找一个类似的域名,把原网站其中一个网页完全复制过来,修改其中的内容,然后给甲方看。但是,这个新...

蓝叶子Sheep
2018/02/07
0
0
使用debian sid做为自己的

最近闲来无事,从ubuntu 转向debian装了debian不下十遍,最后确定debian sid做为自己的桌面系统。刚开始用ubuntu12.04 老是无缘无辜的崩溃,关机失去响应。装了硬件驱动本地视频不能播放(我...

杨来红
2012/03/29
3K
1
codevs 5971 打击犯罪

题目描述 Description 某个地区有n(n<=1000)个犯罪团伙,当地警方按照他们的危险程度由高到低给他们编号为1-n,他们有些团伙之间有直接联系,但是任意两个团伙都可以通过直接或间接的方式联系...

zoom1109
06/19
0
0
Kali Linux下社工密码字典生成工具Cupp/Cewl教程

  Cupp是一款用Python语言写成的可交互性的字典生成脚本。尤其适合社会工程学,当你收集到目标的具体信息后,你就可以通过这个工具来智能化生成关于目标的字典。当对目标进行渗透测试的时候...

FreeBuf
2018/05/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

一起来学Java8(三)——方法引用

在一起来学Java8(一)——函数式编程中有一个简单的函数式编程的例子: import java.util.function.Consumer;class Person { public static void sayHello(String name) { S...

猿敲月下码
9分钟前
4
0
读书笔记:深入理解ES6(十一)

第十一章 Promise与异步编程   Promise可以实现其他语言中类似Future和Deferred一样的功能,是另一种异步编程的选择,它既可以像事件和回调函数一样指定稍后执行的代码,也可以明确指示代码...

张森ZS
33分钟前
9
0
面试官,Java8 JVM内存结构变了,永久代到元空间

在文章《JVM之内存结构详解》中我们描述了Java7以前的JVM内存结构,但在Java8和以后版本中JVM的内存结构慢慢发生了变化。作为面试官如果你还不知道,那么面试过程中是不是有些露怯?作为面试...

程序新视界
40分钟前
25
0
Elasticsearch 实战(一) - 简介

官腔 Elasticsearch,分布式,高性能,高可用,可伸缩的搜索和分析系统 基本等于没说,咱们慢慢看 1 概述 百度:我们比如说想找寻任何的信息的时候,就会上百度去搜索一下,比如说找一部自己喜...

JavaEdge
45分钟前
18
0
【jQuery基础学习】11 jQuery性能简单优化

本文转载于:专业的前端网站➦【jQuery基础学习】11 jQuery性能简单优化 关于性能优化 合适的选择器 $("#id")会直接调用底层方法,所以这是最快的。如果这样不能直接找到,也可以用find方法继...

前端老手
54分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部