1. 全栈程序员必看首页

jzoj 1146. 危险系数(acrobat)

全栈程序员-站长 • • 未分类 • 阅读 40

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.

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/132054.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 我把ConcurrentHashMap & HashTable的知识点都整理了一下[通俗易懂]

    我把ConcurrentHashMap & HashTable的知识点都整理了一下[通俗易懂]

    我把ConcurrentHashMap & HashTable的知识点都整理了一下[通俗易懂]都知道HashMap的知识点，你们知道ConcurrentHashMap&HashTable面试怎么问么？

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月24日
    26
  • pytest skipif_pytest conftest.py文件

    pytest skipif_pytest conftest.py文件

    pytest skipif_pytest conftest.py文件前言pytest.mark.skip可以标记无法在某些平台上运行的测试功能，或者您希望失败的测试功能Skip和xfail:处理那些不会成功的测试用例你可以对那些在某些特定平台上不能运行的测试用

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月30日
    9
  • 分子模拟软件amber_[gromacs使用教程] 基于amber力场模拟蛋白小分子复合物

    分子模拟软件amber_[gromacs使用教程] 基于amber力场模拟蛋白小分子复合物

    分子模拟软件amber_[gromacs使用教程] 基于amber力场模拟蛋白小分子复合物祥请参考官网教程，使用其中的mdp参数文件(均100ps)，案例只考虑模拟顺利，暂不考虑合理性。平台：windows软件：gaussina16,ambertools,gromacs2019.6,notepad++,spdbv4.10蛋白文件：4w52.pdb(配体选用EPE)小分子amber力场及坐标文件构建参考本公众号的案例蛋白的修复使用Notepad++删除小分子，水，保存文…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月9日
    58
  • (others)ICMP报文详解系列「建议收藏」

    (others)ICMP报文详解系列「建议收藏」

    (others)ICMP报文详解系列「建议收藏」Linuxicmp学习笔记之一icmp协议相关的格式分类： linux网络2014-04-1723:45 487人阅读 评论(0) 收藏 举报Linuxicmp功能分析之一 icmp协议相关的格式 ICMP协议是网络层中一个非常重要的协议，其全称为Internet Control Message Protocol（因特网控制报文协议

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月24日
    30
  • java集合系列——java集合概述（一）[通俗易懂]

    java集合系列——java集合概述（一）[通俗易懂]

    在JDK中集合是很重要的，学习java那么一定要好好的去了解一下集合的源码以及一些集合实现的思想！ 一：集合的UML类图（网上下载的图片） Java集合工具包位置是java.util.*二：集合工具的分析 1：Java集合是java提供的工具包，常用的数据结构：集合、链表、队列、栈、数组、映射等 2：java集合主要划分为五个部分： List列表、Set集合、Map映射、迭代器（It

    全栈程序员-站长的头像 全栈程序员-站长
    2022年2月26日
    58
  • 深入理解Java类加载器(1)：Java类加载原理解析

    深入理解Java类加载器(1)：Java类加载原理解析

    深入理解Java类加载器(1)：Java类加载原理解析1      基本信息每个java开发人员对java.lang.ClassNotFoundExcetpion这个异常肯定都不陌生，这背后就涉及到了java技术体系中的类加载。Java的类加载机制是java技术体系中比较核心的部分，虽然和大部分开发人员直接打交道不多，但是对其背后的机理有一定理解有助于排查程序中出现的类加载失败等技术问题，对理解java虚拟机的连接模型和java语言的动态性

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月11日
    5

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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