[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=1629

[算法]

贪心

考虑两头相邻的牛 , 它们的高度值和力量值分别为ax , ay , bx , by

我们发现 , 当ax + ay < bx + by时 , x排在前面比y排在前面更优

也就是说 , 当序列中有相邻的牛使得ax + ay >= bx + by时 , 可以通过交换两头牛使得答案更优

综上 , 按牛的(高度值 + 力量值)以关键字升序排序 , 即可

时间复杂度 : O(NlogN)

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
typedef long long LL;
const LL inf = 1e18; struct info
{
LL x , y;
} a[MAXN]; int n; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline bool cmp(info a , info b)
{
return a.x + a.y < b.x + b.y;
} int main()
{ read(n);
for (int i = ; i <= n; i++)
{
read(a[i].x);
read(a[i].y);
}
sort(a + , a + n + , cmp);
LL ans = -inf , now = ;
for (int i = ; i <= n; i++)
{
chkmax(ans , now - a[i].y);
now += a[i].x;
}
cout<< ans << '\n'; return ; }

最新文章

  1. 【Win 10 应用开发】三维变换
  2. 9.19 JS数组
  3. 凡聊过必留下痕迹-破解加密的WeChat数据库
  4. MDX语法
  5. presentedViewController 和 presentingViewController 以及 dismissViewControllerAnimated 的使用
  6. Notepad++的一些常用的快捷键
  7. 解决wix生成的msi的license对话框空白的问题
  8. ArrayList遍历的同时删除--- 删除还是用迭代器的比较好,其它的都会有问题.
  9. ASP.NET Core 网站发布到Linux服务器
  10. unix及Linux发展历程
  11. 在Visual Studio2017和2015中开发报表项目
  12. Leetcode中sort排序遇到的一些问题
  13. Koa源码分析(三) -- middleware机制的实现
  14. CentOS 6.5 x64下查找依赖包,或用YUM安装
  15. English trip M1 - AC11 May I Help You? 我能帮到你吗? Teacher:Lamb
  16. div和span与块级和行内标签
  17. Python 实现数据库更新脚本的生成
  18. HDU 5299 圆扫描线 + 树上删边
  19. MATLAB 的向量,矩阵和阵列命令
  20. 【Unity笔记】静态碰撞体的陷阱

热门文章

  1. JFinal2.0极速开发视频教程发布【转】
  2. HUNAN 11560 Yangyang loves AC(二分+贪心)
  3. 新闻:融资600万 他用一套系统优化15大HR工作场景 精简入转调离 月开通214家 | IT桔子
  4. Docker 的CMD与ENTRYPOINT区别
  5. 项目整理--Echarts前端后台的贯通写法
  6. [Cypress] install, configure, and script Cypress for JavaScript web applications -- part2
  7. 【转载】C#调用国家气象局天气预报接口
  8. Intel processor brand names-Xeon,Core,Pentium,Celeron----Quark
  9. 写2个线程,其中一个线程打印1~52,另一个线程打印A~z,打印顺序应该是12A34B45C……5152Z
  10. [leetcode] database解题记录