题解

这道题的目的是找出哪些圆盘是“可删减”的，即在给定的配置中，这些圆盘的存在不会影响最终的宽度。我们将圆盘按照从左到右的顺序固定在$xOy$坐标系中，并按照以下规则判断哪些圆盘是可删减的：

1. 理解问题：从左到右，我们将每个圆按顺序放置，第一个圆与$y=0$轴相切。之后每个圆都会被放置到左边，直到它与前面某个圆相切。问题的关键是判断哪些圆在与后面圆相切时，实际上并不会影响最终的配置宽度。

2. 栈的应用：我们使用一个栈来模拟圆盘的排列顺序。栈中记录的是尚未被完全“遮住”的圆盘。对于每个新圆，我们需要找出它与栈中哪个圆相切，并且更新其坐标。如果这个圆不会改变最终的宽度，那么它就是“可删减的”。

3. 算法步骤：

   • 初始化第一个圆与$y=0$相切。
   • 对于每一个新的圆，遍历栈中的圆，计算它们相切时的横坐标，并更新该圆的位置。
   • 如果当前圆与之前的圆不相切，说明它影响了最终的宽度；否则，它是可删减的。
   • 最终通过栈中的记录，判断哪些圆是可删减的。

代码解释

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define maxn 100010
const double eps=1e-8;  // 精度范围，防止浮动误差
struct Point{
    double x,y,r;  // 记录圆的x坐标、y坐标和半径
}p[maxn];
int n,sta[maxn],flag[maxn];  // n是圆盘数量，sta是栈，flag用来标记圆是否可删减

int main(){
    while(~scanf("%d",&n)){
        int last=1, pos=0;  // last记录最后一个不可以删减的圆，pos为栈的当前指针
        for(int i=1;i<=n;i++) scanf("%lf",&p[i].r);  // 输入圆盘的半径
        for(int i=1;i<=n;i++){
            p[i].x = p[i].y = p[i].r;  // 初始化圆的坐标
            flag[i] = 1;  // 默认为可删减
            int k=0;  // k用于记录当前圆相切的圆的下标
            for(int j=1;j<=pos;j++){
                // 计算圆i与栈中圆sta[j]相切时的横坐标
                double x = p[sta[j]].x + 2 * sqrt(p[sta[j]].r * p[i].r);
                if(x > p[i].x + eps){  // 如果当前横坐标更大，更新
                    p[i].x = x;
                    k = j;
                }
            }
            pos = k;  // 更新栈的指针
            sta[++pos] = i;  // 将当前圆加入栈
            // 如果当前圆与前一个圆相切的宽度更大，更新last
            if(p[i].x + p[i].r - p[last].x - p[last].r > eps) last = i;
        }

        // 将栈中不可以删减的圆标记为不可删减
        for(int i=1;i<=pos;i++) flag[sta[i]] = 0;
        // 将last之后的圆标记为不可删减
        for(int j=last+1;j<=n;j++) flag[j] = 1;

        int num = 0;
        for(int i=1;i<=n;i++) if(flag[i]) num++;  // 统计可删减的圆盘数量
        printf("%d\n", num);  // 输出可删减的圆盘数量
        for(int i=1;i<=n;i++) if(flag[i]) printf("%d\n", i);  // 输出可删减圆盘的序号
    }
    return 0;
}

代码分析

1. 数据结构：

   • Point结构体保存每个圆的半径和坐标（x、y）。sta栈用于存储尚未完全被遮住的圆的序号，flag数组用于标记每个圆是否为可删减圆。

2. 关键计算：

   • 对于每个圆，我们计算它与栈中圆的相切位置，并根据横坐标来决定是否更新它的位置。计算两个圆相切时的横坐标公式是：
     [ x = x_{sta[j]} + 2 \times \sqrt{r_{sta[j]}} \times \sqrt{r_{i}} ] 如果当前圆与之前的圆相切，且横坐标更新了，我们就更新该圆的横坐标，并把它的位置标记为最新的相切位置。

3. 核心逻辑：

   • 遍历所有圆时，依次把每个圆放入栈中，并根据与栈中圆的相切情况来决定它是否会影响最终的宽度。如果不会影响，就标记为可删减。
   • 最后根据栈中的状态输出哪些圆是可以删减的。

复杂度分析

• 时间复杂度：对于每个圆，我们最多遍历栈中所有圆，最坏情况下栈中的圆的数量为$N$。因此，整体时间复杂度是$O(N^2)$。
• 空间复杂度：使用了O(N)的空间存储圆的信息和栈。

总结

这道题考察了如何利用栈和几何计算来确定哪些圆的存在不会影响最终的配置宽度。通过模拟圆与前面圆的相切过程，最终找出了可删减的圆。