jzoj 1146. 危险系数(acrobat)

jzoj 1146. 危险系数(acrobat)1146.危险系数(acrobat) (FileIO): input:acrobat.in output:acrobat.out时间限制: 1000ms  空间限制: 262144KB  具体限制  GotoProblemSet题目描述   N(1输入第一行:输入一个整数N;第2到

大家好,又见面了,我是你们的朋友全栈君。

题目描述

      N(1 <= N <= 50,000,标记为1..N)个人计划玩一个叠罗汉杂技,除了最底下的那个人以外每个人都站在另一个人的头顶上。每个人都有自己的体重W_i(1<=W_i<=10,000)和力量S_i(1<=S_i<=1,000,000,000),每个人的危险系数定义为他所承受的重量(注意:不包括他自己)减去他的力量所得到的差,你的任务是找出使得N个人中最大的危险系数最小的顺序。

输入

第一行:输入一个整数N;

第2到第N+1行:其中第i+1行描述第i个人的体重和力量,中间用空格隔开。

输出

输出一个整数表示最优顺序中最大的危险系数。

样例输入

3
10 3
2 5
3 3

样例输出

2

数据范围限制

贪心,为了达到最优,应该使越下面的人的力量和体重尽可能大,所以以体重和力量的和为关键字排序,

然后直接求解就好了。

代码如下:

var a,b,c:array[1..50000]of longint; n,max:longint;procedure init;var i:longint;begin readln(n); for i:=1 to n do  begin   readln(a[i],b[i]);   c[i]:=a[i]+b[i];  end;end;procedure qsort(l,r:longint);var i,j,k,m:longint;begin if l>=r then exit; i:=l; j:=r; k:=c[(i+j) div 2]; repeat  while c[i]<k do inc(i);  while c[j]>k do dec(j);  if i<=j then   begin    m:=c[i]; c[i]:=c[j]; c[j]:=m;    m:=a[i]; a[i]:=a[j]; a[j]:=m;    m:=b[i]; b[i]:=b[j]; b[j]:=m;    inc(i); dec(j);   end;  until i>j; qsort(l,j); qsort(i,r);end;procedure main;var i,k,j:longint;begin k:=0; max:=-maxlongint; for i:=1 to n do  begin    if k-b[i]>max then max:=k-b[i];    k:=k+a[i];  end; write(max);end;begin assign(input,'acrobat.in');reset(input); assign(output,'acrobat.out');rewrite(output); init; qsort(1,n); main; close(input); close(output);end.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132054.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • openwrt旁路由的设置「建议收藏」

    openwrt旁路由的设置「建议收藏」1:旁路由必须和主路由在同一网段2:旁路由的网关必须指向主路由3:防火墙开启IP动态伪装

  • python绘制爱心表白_六行python代码的爱心曲线

    python绘制爱心表白_六行python代码的爱心曲线#-*-coding:utf-8-*-importturtleimporttime#画爱心的顶部defLittleHeart():foriinrange(200):turtle.right(1)turtle.forward(2)#输入表白的语句,默认ILoveyoulove=input(‘请输入表白语句,默认为输入为”ILoveyou”:’)#输入署名或者赠谁,没有不执行me=input(‘请输.

  • java中stringBuilder常用方法[通俗易懂]

    java中stringBuilder常用方法[通俗易懂]String对象是不可改变的。每次使用System.String类中的方法之一时,都要在内存中创建一个新的字符串对象,这就需要为该新对象分配新的空间。在需要对字符串执行重复修改的情况下,与创建新的String对象相关的系统开销可能会非常昂贵。如果要修改字符串而不创建新的对象,则可以使用System.Text.StringBuilder类。例如,当在一个循环中将许多字符串连接在一起时,使用StringBuilder类可以提升性能。通过用一个重载的构造函数方法初始化变量,可以创建StringBuild

  • xml中注释快捷键_如何快速取消注释程序代码

    xml中注释快捷键_如何快速取消注释程序代码eclipse中编辑Java文件时,注释快捷键和取消注释快捷键都是:”CTRL+/”编辑xml文件时,注释:CTRL+SHIFT+/  取消注释:CTRL+SHIFT+\

  • linux常用命令

    linux常用命令linux常用命令

  • 面向对象之反射和内置方法

    静态方法静态方法(staticmethod)和类方法(classmethod)类方法:有个默认参数cls,并且可以直接用类名去调用,可以与类属性交互(也就是可以使用类属性)静态方法:让类里的方法

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号