/ / 题库 /

排队出发

排队出发

测试数据来自 wjszez/1876

【问题描述】

神牛岛是传说中的一个岛屿,凡是成功到那里游历,完成探险并返回的人,都会成为神
牛。但是,现实中却没有人知道如何到达神牛岛。

这天夜里,笃志者睡着之后,不久就进入了梦乡。他突然看到有人在问,“有人想去神
牛岛的吗?”神牛岛之旅的牌子前,就开始有不少勇士报名要去冒险探索。

“我们会把勇士安排在前,带领大家一起去神牛岛。下面开始点名!”管理队伍的 LXY 神
牛说。其实说实话,给学生排队这种工作是最让神牛头疼的了。因为同学们都有自尊心,都
不愿意排后面。共有 n 个同学要排成一列,每个同学有两个属性:影响力和承受能力。给
一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受能力。现在
请你帮忙安排一下点名顺序,尽量使受到心理创伤最大的同学少受创伤。

【输入格式】

输入文件 queue.in 包含 n+1 行:

第 1 行是整数n,表示同学的个数。

第 2~n+1 行每行两个自然数,分别是该同学的影响力和承受能力。

【输出格式】

输出文件 queue.out包含 1 行,为你安排的顺序中受到心理创伤最大的同学受到的创
伤。

【输入样例】
3

10 3

2 5

3 3

【输出样例】
2

【数据规模】

对于 100%的数据,1<=n<=50000,1<=影响力<=10000,1<=承受能力<=1,000,000,000。

信息

ID
1914
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者