[CF1137E]Train Car Selection[维护凸壳]

题意

题目链接

分析

  • 首先,如果加到了车头所有之前的车厢都不可能成为答案。

  • 如果加到了车尾,容易发现对于 \(x_2<x_3\) 而言在某个时刻会出现 2 又比 3 优的情况。

  • 具体来讲,如果存在 \(sx_3+b+y_3\ge sx_2+b+y_2​\) ,那么 2 比 3 优。

    推一推:\(-s<\frac{y_3-y_2}{x_3-x_2}​\) ,所以维护一个下凸壳即可。

  • 时间复杂度 \(O(n)​\)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {int x = 0,f = 1;char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 3e5 + 7;
int n, m;
int tl;
LL k, b, val[N], tot;
typedef pair<LL, LL> pii;
#define mp make_pair
#define fi first
#define se second
pii q[N];
double getk(pii a, pii b) { return 1.0 * (b.se - a.se) / (b.fi - a.fi);}
LL calc(pii a) {return a.fi * k + a.se + b;
}
int main() {n = gi(), m = gi();q[tl = 1] = mp(0, 0);while(m--) {int opt = gi();if(opt == 1) {q[tl = 1] = mp(0, 0);n += gi();k = b = 0;}if(opt == 2) {pii now = mp(n, -(k * n + b));while(tl > 1 && getk(q[tl], now) <= getk(q[tl - 1], q[tl])) --tl;n += gi();q[++tl] = now;}if(opt == 3) b += gi(), k += gi();while(tl > 1 && calc(q[tl]) >= calc(q[tl - 1])) --tl;printf("%lld %lld\n", q[tl].first + 1, calc(q[tl]));}return 0;
}

转载于:https://www.cnblogs.com/yqgAKIOI/p/10569621.html

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://dhexx.cn/news/show-17489.html

如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网进行投诉反馈,一经查实,立即删除!


相关文章:

  • ios手机Safari本地服务连不上
  • 20个Flutter实例视频教程-01节底部导航栏和切换效果的制作-1
  • 遍历结构体内部元素和值(Name and Value)
  • #paragma详解
  • C#项目需求分析
  • 6.16.5
  • Vue简易博客总结
  • struct过滤器和拦截器的区别
  • java中数组操作常见的三个错误
  • shell 构建脚本基础
  • c语言数据结构学习心得——栈
  • MySQL学习笔记:一道group by+group_concat解决的小问题
  • [SDOI2009] HH去散步 (矩阵乘法)
  • BUAA OO 2019 第一单元作业总结
  • HAOI2018 反色游戏
  • 软件工程导论 四则运算
  • 安卓系统怎么样不Root激活XPOSED框架的方法
  • 页面滚动可视区域的获取
  • VScode加文件头的方式
  • jar包引用版本不一致引发的问题
  • [Swift]LeetCode831. 隐藏个人信息 | Masking Personal Information
  • 解决:win10在空白处右键资源管理器重启的故障
  • idea取消vim模式
  • 关于RabbitMQ Queue Argument的简介
  • unittest框架(惨不忍睹低配版)
  • vmware vsphere出现“需要整合虚拟机磁盘”的告警处理方法(完整版)
  • webpack遇见的坑:Please install 'webpack-cli' in addition to webpack itself to use the CLI.
  • Docker for Windows(一)下载与安装
  • 21 , CSS 构造模型
  • 简述数据库优化
  • Golang 入门 : 打造开发环境
  • JavaWeb项目服务端获取客户端的IP地址
  • Kafka分区分配策略(Partition Assignment Strategy
  • [Linux]不可重入函数
  • 交叉熵反向求导计算过程
  • UML第二次作业 类图中类的表示
  • poj 1852 Ants
  • 你真的懂JavaScript基础类型吗
  • UVALive 5760 Alice and Bob
  • Jason与Xml的解析过程
  • 安装grid时找不到ASM共享磁盘
  • 洛谷.5283.[十二省联考2019]异或粽子(可持久化Trie 堆)
  • BOMDOM
  • Hive——元数据表含义
  • 2072=删数问题
  • Python_装饰器精讲_33
  • 使用Google zxing生成二维码
  • 影之刃简介
  • 鼠标单击元素输出对应元素的索引号
  • pod BaiduMapKit 报错解决方案