当前位置:网站首页>125. 耍杂技的牛
125. 耍杂技的牛
2022-08-10 03:41:00 【Hunter_Kevin】
题目
农民约翰的 N 头奶牛(编号为 1…N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。
奶牛们不是非常有创意,只提出了一个杂技表演:
叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 N,表示奶牛数量。
接下来 N 行,每行输入两个整数,表示牛的重量和强壮程度,第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。
输出格式
输出一个整数,表示最大风险值的最小可能值。
数据范围
1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000
输入样例:
3
10 3
2 5
3 3
输出样例:
2
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
struct Node{
int w, s;
bool operator< (const Node & t)const{
return w+s < t.w+t.s;
}
}a[N];
int sum[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d%d",&a[i].w, &a[i].s);
sort(a+1, a+1+n);//根据重量和强度的和排序
// 求重量的前缀和
for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i].w;
// 遍历找出 sum[i-1] - a[i].s的最大值,即风险的最大值
int res = -1e9;
for(int i = 1; i <= n; i++) res = max(res, sum[i-1]-a[i].s);
cout << res << endl;
return 0;
}
边栏推荐
- 文件操作【c语言】
- RoyalScope分析仪:CAN总线波形台阶和信号幅值低的问题
- sql注入之宽字节注入,limit,order by
- Recommend several easy-to-use MySQL open source clients, it is recommended to collect
- 线程和线程间通信(C语言)
- Pytorch中的torch.index_select对应MindSpore哪个方法
- goland json.Marshal导致&变成\u0026
- 如何快速成为一名软件测试工程师?测试员月薪15k需要什么技术?
- 请问mindspore支持l1范数归一化吗
- 【单调栈】【概念讲解&&模板代码】
猜你喜欢
goland console shows overlapping problem solution
RoyalScope分析仪:CAN总线波形台阶和信号幅值低的问题
PID与ADRC
Jackson的ObjectMapper在项目中的主要运用
Recommend several easy-to-use MySQL open source clients, it is recommended to collect
c语言进阶篇:动态内存管理(相关函数、常见错误、笔试题)
一种能让大型数据聚类快2000倍的方法,真不戳
maya图片如何渲染
【MindSpore功能】运行SSD-MobileNetV1 FPN样例报错
2022华数杯思路分析
随机推荐
PID整定方法
RoyalScope分析仪:发现CAN总线波形台阶和信号幅值低的问题
Difference between netstat and ss command
原型和原型链
Flink Table&Sql API使用遇到的问题总结
【Verilog数字系统设计(夏雨闻)5-------模块的结构、数据类型、变量和基本运算符号1】
TCP协议之《Pacing功能》
测试工作管理与规范
TCP协议之《ACK状态4种详解》
How does a new tester do functional testing?Test thinking is really important
Neo4J 与 Cypher 查询语言基础
leetcode 283:移动零
maya图片如何渲染
applet wxs
electron 应用开发优秀实践
order by注入与limit注入
Recommend several easy-to-use MySQL open source clients, it is recommended to collect
测试常见问题100类(1)
整理零碎东西
day17正则表达式作业