待解决练习题 气球半径

题目

题目描述

有?n?个气球，他们一开始都是空的。

接下来，它们会按照从?11?到?n?的顺序依次充气，其中第?i?个气球与地面在?xi??位置接触。

当气球碰到碰到前面的某个气球，或者达到半径最大限制时，就会停止充气。其中第?i?个气球的半径最大限制为?ri?。

现在请你求出，每个气球最终半径是多少。

输入描述

第一行一个正整数?n，表示气球个数。

接下来?n?行，每行两个空格隔开的整数 xi?,ri?。

其中，1≤n≤200?000;0≤xi?≤109;1≤ri?≤109;x1?<x2?<?<xn?。

输出描述

输出?n?行，每行一个浮点数，第?i?行的浮点数表示最终第?i?个气球的半径。

你的答案会被判为正确，当且仅当与答案的绝对误差不超过 10^?3??。

输入输出样例

示例 1

输入

3
0 9
8 1
13 7

输出

9.000
1.000
4.694

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

提交代码

//气球半径

//气球为球形的
//气球可能不和上一个气球相碰，而和上上个或更远的相碰
//被略过的气球也不可能被别的气球相碰，被碰过的气球可能会被再碰
//单调栈
//栈内存气球下标
//输入按照气球圆心下标的顺序 

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

struct Balloon{
	long long x;//圆心坐标 
	double r;//气球半径（最大半径或实际半径） 
}; //气球结构体

int n;//气球个数
vector<Balloon> bals;//各气球结构体数组 
//vector<float> result;//结果 
stack<Balloon> stk;//单调栈
stack<Balloon> t;//暂时存储被弹出的气球 

//求这两个气球相碰时的半径
double getR(long long x1,long long x2,double r1){
	double r2;
	double x,y;
	x = (double)x1;
	y = (double)x2;
	
	//求半径
	r2 = (y - x) * (y - x) / (4.0 * r1);
	
	return r2; 
} 

//单调栈
void monotonicStack(){
	Balloon b;
	double r1,r2;
	long long x1,x2; 
	
	//从左到右确定结果
	for(int i = 0;i < n;i++){
		x2 = bals[i].x;
		//double last = 1e9;//上一次求出的半径长度
		double last = bals[i].r;//上一次求出的半径长度
		//Balloon t;//暂时存储可能相碰的气球 
		
		while(!stk.empty()){
			b = stk.top();
			r1 = b.r;
			x1 = b.x;
			//求这两个气球相碰时的半径 
			r2 = getR(x1,x2,r1);
			//printf("r2=%d\n",r2);
			
			/*if(r2 > bals[i].r){
				//没相碰
				//更新气球的半径 
				bals[i].r = min(bals[i].r,last);
				break;
			}else */
			
			//相碰了且答案正确
			//相碰了但答案在下一个
			//未相碰且之后也不会有相碰的了
			//未相碰但之后有相碰的
			//如果最后和哪个都没相碰->不用把栈弹空
			//如果最后和前面某个相碰了->把之间的弹空 
			
			if(r2 > last){
				//没相碰
				/*if(!t.empty()){
					//前面有相碰的了
					//不会没有相碰的
					t.push(stk.top()); 
				} */
				t.push(stk.top());
				stk.pop(); 
			}else{
				//可能相碰了
				last = r2;
				//t = stk.top();
				//把暂存栈弹空
				while(!t.empty()){
					t.pop();
				} 
				t.push(stk.top());
				stk.pop();
			}
		}
		
		//找到最左面的气球可能相碰
		//更新气球的半径 
		bals[i].r = min(last,bals[i].r);
		//stk.push(t);
		while(!t.empty()){
			stk.push(t.top());
			t.pop();
		}
		
		stk.push(bals[i]);
	} 
} 

int main(){
	//输入整数数组  
	/*int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums.push_back(t);
	}*/
	
	//输入气球数量
	scanf("%d",&n);
	
	//输入各气球数据 
	Balloon b;
	long long r;
	for(int i = 0;i < n;i++){
		scanf("%lld %lld",&b.x,&r);
		b.r = (double)r;
		bals.push_back(b);
	} 
	
	//-------------------------------
	
	//单调栈
	monotonicStack(); 
	
	//输出结果
	for(int i = 0;i < n;i++){
		printf("%.3lf\n",bals[i].r);
	}
	
	return 0;
} 

总结

解题思路：两个相碰气球中间的气球后面一定也不会碰到，可以直接删掉，故可以利用改良后的单调栈。

测试情况：5个测试用例通过了第1个，有3个测试用例超时了，还有1个测试用例显示答案错误。