在一条数轴上从左向右有一些气球,每个气球一开始位于横坐标xi的位置,是半径为0的圆.现在开始从左向右给每个气球充气.被充气的气球的半径会不断变大,直到达到这个气球的半径上限Ri或者这个气球和之前被充气的某个气球相切.在半径变大的过程中,气球始终和数轴在横坐标xi的位置相切(即气球的位置不变). 问最后每个气球的半径. 40% n<=2000 100% n<=200000
非常妙的题然而还是不会做 首先考虑暴力怎么做:模拟气球充气的过程,从左到右考虑每个气球的最大半径. 对于第i个气球,它前面的i-1个气球都会对它的半径有一个限制,第j个气球(\(j<i\))使得第i个气球的半径不能超过\(f(i,j)\).假设第j个气球位于\(xj\),第i个气球位于\(xi\),第j个气球充气后半径为R,那么\(f(i,j)=(xi-xj)^2/(4R)\) 我们对所有的f(i,j)和ri取最小值就可以得到i充气之后的半径.这样是\(O(n^2)\)的. 接下来可以观察出一个性质:对于i左侧的两个已经充气的气球j1,j2,如果j1在j2左侧且j1的半径小于j2,那么第i个气球在碰到j1之前必须先碰到j2,也就是会因为j2的阻挡碰不到j1,画画图是比较明显的.严谨一点,这时候一定有\(f(i,j1)>f(i,j2)\). 那么我们既然是从左向右考虑所有气球,就可以对前面的所有气球维护一个单调栈,只存储那些"右侧不存在半径更大的气球"的气球,每次只考虑栈里的气球对第i个气球的影响,然后把第i个气球扔到栈里,该弹出栈的弹出来.然而这样好像复杂度还是\(O(n^2)\) 我做到这里之后就想偏了...考虑有没有单峰性质或者决策单调性,发现都没有,就看题解去了你们看这就是辣鸡 题解非常妙地做到了O(n). 具体是这样: 我们从栈顶的气球开始考虑其对第i个气球的影响.第i个气球的半径初始化为上限ri,然后对f(i,栈顶的气球)取min. 假如取min之后第i个气球的半径比栈顶大: 那么根据刚才观察的性质,这个栈顶之后就没有用了,把它弹出来.如果此时栈非空,那么继续考虑新的栈顶对第i个气球的影响.如此循环,直到栈为空或者第i个气球取min之后的半径比栈顶的半径小. 假如取min之后第i个气球的半径比栈顶小: 考虑栈里其他的气球(在栈顶气球的左侧).既然栈顶的气球在第i个气球的左侧且现在半径比第i个气球大,那么栈顶气球左侧的气球想要碰到第i个气球就必须先碰到栈顶的气球,也就是会因为栈顶的气球的阻挡而不能碰到第i个气球(和刚才观察的性质是对称的) 因此,此时栈里的其他气球不会再对第i个气球的半径产生影响,我们此时得到了第i个气球的最终答案.把第i个气球扔到栈里就可以继续考虑第i+1个气球了.
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=200005; double x[maxn],r[maxn]; double R[maxn]; int stk[maxn],top=0; int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%lf%lf",x+i,r+i); for(int i=1;i<=n;++i){ R[i]=r[i];int g=i; while(top){ double tmp=(x[i]-x[stk[top-1]])*(x[i]-x[stk[top-1]])/4.0/R[stk[top-1]]; R[i]=min(R[i],tmp); if(R[i]<R[stk[top-1]])break; else --top; } stk[top++]=i; } for(int i=1;i<=n;++i)printf("%.3f\n",R[i]); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7010605.html
相关资源：数据结构—成绩单生成器