首页 > 其他分享 >耍杂技的牛

耍杂技的牛

时间:2024-10-09 17:52:16浏览次数:8  
标签:10 强壮 杂技 NN int 000 奶牛

农民约翰的 NN 头奶牛(编号为 1..N1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。

奶牛们不是非常有创意,只提出了一个杂技表演:

叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 NN 头奶牛中的每一头都有着自己的重量 WiWi 以及自己的强壮程度 SiSi。

一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数 NN,表示奶牛数量。

接下来 NN 行,每行输入两个整数,表示牛的重量和强壮程度,第 ii 行表示第 ii 头牛的重量 WiWi 以及它的强壮程度 SiSi。

输出格式

输出一个整数,表示最大风险值的最小可能值。

数据范围

1≤N≤500001≤N≤50000,
1≤Wi≤10,0001≤Wi≤10,000,
1≤Si≤1,000,000,0001≤Si≤1,000,000,000

输入样例:
3
10 3
2 5
3 3
输出样例:
2
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
typedef pair<int,int> PII;
PII a[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) 
    {
        int w,s;
        cin>>w>>s;
        a[i]={w+s,w};
    }
    sort(a,a+n);
    int res=-2e9,sum=0;
    for(int i=0;i<n;i++)
    {
      int s = a[i].first - a[i].second, w =a[i].second;
        res = max(res, sum - s);
        sum += w;
    }
    cout<<res<<endl;
    return 0;
}

 

标签:10,强壮,杂技,NN,int,000,奶牛
From: https://blog.csdn.net/qq_60510847/article/details/142744569

相关文章

  • AcWing 125. 耍杂技的牛
    算法1(贪心)题目要求牛的最大伤害值最小,那么我们使每头牛的伤害值最小,在其中找最大值作为答案如何使得每头牛的伤害值最小?(1)自身w值越大应该放到底部,使得被减数减小(2)自身s值越大应该放到底部,使得减数变大综上,w+s从小到大排序,最大的危险系数一定是最小的。贪心算法......
  • 洛谷P1842 [USACO05NOV] 奶牛玩杂技
    [USACO05NOV]奶牛玩杂技题目背景FarmerJohn养了\(N\)头牛,她们已经按\(1\simN\)依次编上了号。FJ所不知道的是,他的所有牛都梦想着从农场逃走,去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳(她们还尝试过把自己装在大炮里发射......
  • 面试杂技第一篇
    1.探究微前端https://mp.weixin.qq.com/s/997pVVxdgpOH6ZsDsFAh2g2.通讯产品https://yunxin.163.com/im?from=bd_IM_bdjj202302363.jquery+bootstrap基础参考案列https://www.51fapiao.cn/fpcx/query.html4.二次封装基于AntDesign+VUE3二次封装antd选择器目的:解决后......
  • 耍杂技的牛 模板
    题目: 农民约翰的 N 头奶牛(编号为 1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。奶牛们不是非常有创意,只提出了一个杂技表演:叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N......
  • 贪心推公式——AcWing 125. 耍杂技的牛
    贪心推公式定义贪心算法是一种在每一步选择中都采取在当前状态下最优的选择,希望通过局部的最优选择来得到全局最优解的算法策略。运用情况问题具有最优子结构,即一个问题的最优解包含其子问题的最优解。可以通过局部最优决策逐步推导到全局最优。问题的选择策略相对明确且易......
  • hi.杂技
    杂技题目背景小LLL在中考后在家人的催促下前去参观县城的马戏团。啊啊啊,刚刚发现相册里面这张照片找不到了。题目描述小......
  • 【杂技术】关于intel AC 3168 无线网卡发WIFI 一段时间后 WIFI会完全卡死的情况
    关于intelAC3168 无线网卡发WIFI一段时间后WIFI会完全卡死的情况更新驱动到21以后的版本就可以了我更新的版本是:21.80.0.4驱动日期:2020/1/30星期四用的360驱动大师更新的,去intel官网下载最新的(20.X.X.X)好像都不行,不知道intel官网是做什么的。发出来防止以为是系统还是......