Luogu4697 CEOI2011 Balloons 单调栈
2024-08-24 08:06:43
题意:给出$N$个气球,从左往右给出它们的$x_i$与$r_i$。现在从左往右给它们充气,每一个气球在充气的过程中始终在$x_i$点与地面相切,且最大半径为$r_i$。如果在充气的过程中气球与前面的某一个气球相切,则停止充气。问最后每个气球的半径。$N \leq 2 \times 10^5,x_i,r_i \leq 10^9$,保证$x_i$单调递增。
首先可以计算得如果某一个气球$i$与前面的气球$j$相切时气球$i$的半径大小为$\frac{(x_i - x_j) ^ 2}{4r_j}$
然后我们可以手玩发现一个降低复杂度的方法:如果当前的气球的半径比之前的某些气球半径要大,这些气球是不会产生贡献的,而在某一次充气过程中,如果现在充气的最大值比某一个球的半径要小,那么其前面的在当前气球上也不可能产生贡献。所以我们可以维护一个$x$递增,$r$递减的单调栈来做决策,这样复杂度就降为$O(n)$了。
#include<bits/stdc++.h> #define ld long double using namespace std; ; int Stack[MAXN] , x[MAXN] , R[MAXN]; ld r[MAXN]; int main(){ ; cin >> N; ; i <= N ; i++){ cin >> x[i] >> R[i]; ld minN = R[i]; while(hd){ minN = min(minN , (x[i] - x[Stack[hd]]) / r[Stack[hd]] * (x[i] - x[Stack[hd]]) / ); if(minN > r[Stack[hd]]) hd--; else break; } cout << ) << (r[i] = minN) << endl; Stack[++hd] = i; } ; }
最新文章
- C# http请求数据
- CoCreateInstance调用返回代码0x80040154的一种解决方法
- GIt 从入门到放弃
- SQL Server 中的触发器(trigger)
- Java Socket Option
- [转]JDK6和JDK7中的substring()方法
- Objective-C语言介绍 、 Objc与C语言 、 面向对象编程 、 类和对象 、 属性和方法 、 属性和实例变量
- Git:代码冲突常见解决方法
- flex-mp3
- Asp.net 实现图片缩放 无水印(方法一)
- android 检查网络是否可用,如果不可用弹出设置,让用户改变
- qt tablewidget中单个和批量删除代码如下(部分)截图如下
- vue项目结构
- RabbitMQ(1) - win+rabbitMQ
- 网络编程——socket开发
- 对 String 字符串的理解
- 【Linux学习四】正则表达式
- python相关工具
- shiro中SSL
- hiveserver2连接报错: User: root is not allowed to impersonate anonymous (state=08S01,code=0)