a356: CTSC2007 Day2.2.挂缀
Tags :
Accepted rate : 9人/9人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:46

Content

“珠缀花蕊,人间几多酸泪”……


挂缀在很早就被人们作为一种装饰品,垂坠的风韵,华丽摇曳的摆动,展现
出一种与众不同的优雅与高贵。而我们的主人公小Q,正想买一条漂亮的挂缀放
在寝室里作为装饰。


挂坠的构成,是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成:分
别是珠子、珠子上方的连接环与珠子下方的挂钩(如下图)。我们可以简单的认
为从上往下数的第i 个缀珠是将它的连接环套在其上方(也就是第i-1 个)缀珠
的挂钩之上(第一个除外)。小Q 想买一根足够长的挂缀,这样显得更有韵味☺

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


小 Q 希望她的挂缀尽量长,你能帮她计算出最长可能的稳定挂缀么?当然,
如果有多个可选方案,小Q 希望总重量最小的。

Input
输入第一行包含一个正整数N,表示商店拥有的珠缀数目。
接下来N 行,每行两个整数(Ci , Wi),分别表示第i 个珠缀的承受能力与重量。
Output
输出包行两行。第一行包含一个整数L,表示可以找到的最
长稳定挂缀长度。第二行包含一个整数W,表示可以找到的长度为L 的稳定挂
缀中的最小重量和。
Sample Input
4
3 5
5 1
3 2
4 6
Sample Output
3
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 4.0s , <1M
公開 測資點#1 (10%): 4.0s , <1M
公開 測資點#2 (10%): 4.0s , <1M
公開 測資點#3 (10%): 4.0s , <10M
公開 測資點#4 (10%): 4.0s , <10M
公開 測資點#5 (10%): 4.0s , <10M
公開 測資點#6 (10%): 4.0s , <10M
公開 測資點#7 (10%): 4.0s , <10M
公開 測資點#8 (10%): 4.0s , <10M
公開 測資點#9 (10%): 4.0s , <10M
Hint :
【数据规模】
对于 30%的数据,N ≤ 10000;
对于 100%的数据,N ≤ 200000;
对于所有的数据,Wi, Ci 不超过2^31。
Tags:
出處:
CTSC2007Day2第二题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」