堆积木

TimeLimit:1000MS  MemoryLimit:128000KB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

  现在有N块积木,每块积木都有自重Weight和正常状态下的承重能力Force,现在要把这N块积木垒在一起,但是有可能某块积木的负重超过了它在正常状态下的承重能力,那么这块积木就有被压坏的危险,请问应该如何堆这N块积木使得N块积木中最大的压力指数最小。

  这里定义压力指数为该积木的负重与其在正常状态下的承重能力的差值。

 

原题:Usaco NOV05 Sliver 奶牛杂技(Cow Acrobats)

Input

  第一行为一个正整数N,表示有N块积木。
  第二行到第 N+1 行,每行两个整数数,分别是第i个积木的Weight和Force。


数据范围及提示:

样例解释:
  把Weight为100的积木放在Weight为1000的积木上,下面积木的压力指数为100 - 100 = 0,另外一块积木的压力指数和它的相等。

 

  对于30% 的数据,1 <= N <= 3
  对于60% 的数据,1 <= N <= 1000
  对于100%的数据,1 <= N <= 50000
  对于100%的数据,1 <= Weight <= 10000,1 <= Force <= 109

Output

  输出共一行,表示最大压力指数的最小值。

SampleInput

2
100 0
1000 100

SampleOutput

0

Submit
题目统计信息详细
总AC数2
通过人数2
尝试人数2
总提交量2
AC率100.00%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: