832C - Strange Radiation【二分+思维】

题意：有n个人坐落在ox坐标上。已知每个人的x,v(速度),dir(朝左还是朝右)。现在有一颗定时炸弹，一旦炸弹引燃，所有人向其当前方向以速度v跑。在爆炸的同时，炸弹会朝正负两个方向释放一条射线，一旦有人碰到了，那么其速度会改变为v+s(射线速度)。现在问，满足让x=0和x=1e6都有人经过的最短时间是多少。

思路：二分时间。时间越长，肯定能跑，时间越短，越难跑。那么单调性很明显。

对于确定的时间，check(time)我们要做的，是判断对于所有朝左方向的人，我们找到炸弹所能安置的最大区间S1，对于方向朝右的人，我们找到炸弹所能安置的所有区间S2。判断这S1和S2是否存在交集。如果存在，那么可行，否则不可行。

求最大的安置区间（对于dir==1来说）分类讨论：

1.对于当前的x，不加速，看看是否能到达。

2.对于当前的x。加速，看看是否能到达，如果不能到达，continue；如果能到达,算出可安置的最大区间。

数据分析：2 ≤ n ≤ 10⁵, 2 ≤ s ≤ 10^{6 0 < x_i < 10⁶, 1 ≤ v_i < s, 1 ≤ dir_i ≤ 2 有些细节处理些在代码里}

^{复杂度分析:O(50*n) 真的赞叹二分的高效。}

CODE：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+50;
struct node
{
    int x,v,t;
}p[maxn];
double ans;
int n,s;

bool check(double times)
{
    ll left_l=1e8,left_r=0,right_l=1e8,right_r=0; // 注意下要开ll。因为时间可以到1e6。然后速度可以到1e6。爆int。 所以一定要注意数据，如果不好判断，直接开ll是最保险的。
    int i;
    for(i=1;i<=n;i++)
    {
        if(p[i].t==1)
        {
            double pos=1.0*p[i].x-times*(p[i].v+s); /** T=0加速 **/  对应加速不能到
            if(pos > 0.0)   continue;
            pos=p[i].x-times*p[i].v;  /**没有加速**/ 对应不加速
            if(pos<=0.0)
            {
                left_l=0,left_r=1e6;
                continue;
            }
            double time=(double)(p[i].x-times*p[i].v)/(double)s;
            ll  dis=p[i].x+floor( (times-time) *(s-p[i].v)   );
            left_l=min(left_l,(ll)p[i].x);
            left_r=max((ll)left_r,dis);
        }
        else
        {
            double pos=1.0*p[i].x+times*(p[i].v+s); /** T=0加速 **/
            if(pos < 1e6)   continue;
            pos=p[i].x+times*p[i].v;  /**没有加速**/
            if(pos>=1e6)
            {
                right_l=0,right_r=1e6;
                continue;
            }
            double time=(double)(1e6-p[i].v*times-p[i].x)/(double)s;
            ll dis=p[i].x-floor( (times-time)*(s-p[i].v)  );
            right_l=min(right_l,dis);
            right_r=max(right_r,(ll)p[i].x);

        }
    }
    //left_l=1e7,left_r=0,right_l=1e7,right_r=0;
    if(   left_l>left_r   ||  left_l > right_r ||  right_l>right_r || right_l>left_r)
        return false;
    return true;
}

int main(void)
{
    cin >> n  >>s;
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&p[i].x,&p[i].v,&p[i].t);
    double l=0.0,r=1e6+60;
    for(int i=1;i<=50;i++)//对double类型进行二分，最好是用for循环，避免死循环之类的复杂.二分的次数根据r-l的范围来搞搞。不放心的话可以100次。
    {
        double mid=(l+r)/2.0; /**double不能位运算**/
        if(check(mid))
            ans=mid,r=mid;
        else
            l=mid;
    }
    printf("%.10f\n",ans);
}