题解：P11021 「LAOI-6」区间测速

· · 题解

题目传送门： P11021 「LAOI-6」区间测速

前言：

第一次在洛谷比赛中切绿题，有些激动，回学校又写不了，于是星期天上午加急写了这一篇题解。

思路：

  1. 我们先把监控信息按时间从小到大排序，因为询问操作需要监控信息的原来的顺序，于是用数组记录下原来位置的监控信息被移到哪里。
for(int i=1;i<=n;i++)
    {
        cin>>e[i].x>>e[i].t;
        e[i].id=i;
    }
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    po[e[i].id]=i;
  1. 因为改变一个监控信息，最大速度可能会变大，也有可能变小，先想变小的情况，我们再记录下每相邻两个监控信息所显示出的速度，再从大到小排序，目的是求出排名前三个最大速度，至于为什么是前三个，因为一个监控信息的改变而只会影响两个速度。与上一步骤一样，将每两个影响速度的监控信息记录下来。 
    for(int i=2;i<=n;i++)
{
    ee[i].kl=(int)(floor(abs(e[i].x-e[i-1].x)/(double)(e[i].t-e[i-1].t)));
    ee[i].id=i;
}
sort(ee+2,ee+1+n,cmp1);
for(int i=2;i<=4;i++)
mo1[ee[i].id]=i,mo2[ee[i].id-1]=i;
  1. 接下来也很简单，所以我先在代码中给你说明 才不是因为太麻烦了
for(int i=1;i<=m;i++)
    {
        int u,v,ans;
        cin>>u>>v;
        int now=po[u];//排序后u点位置 
        int yu=find(v);//二分查找，寻找到第一个大于v时间的监控信息 
        if(mo1[now]==2||mo2[now]==2)// 如果now点对最大速度有影响 
        {
            if(mo1[now]==3 ||mo1[now]==3)// 如果now点对第二大速度还有影响 
            {
                ans=ee[4].kl;//选第三大速度 
            }
            else
            ans=ee[3].kl;//选第二大速度 
        }
        else
        ans=ee[2].kl;//选第一大速度 
        if(now!=yu)//当不在原位时 
        {
            if(yu>1)//当左边监控信息存在时 
            ans=max(ans,(int)(floor(abs(e[now].x-e[yu-1].x)/(double)(v-e[yu-1].t))));
            if(yu<=n)//当右边监控信息存在时 
            ans=max(ans,(int)(floor(abs(e[yu].x-e[now].x)/(double)(e[yu].t-v))));
            ans=max(ans,(int)(floor(abs(e[now+1].x-e[now-1].x)/(double)(e[now+1].t-e[now-1].t))));
        }
        else//当在原位时 
        {
            ans=max(ans,(int)(floor(abs(e[yu].x-e[yu-1].x)/(double)(v-e[yu-1].t))));
            ans=max(ans,(int)(floor(abs(e[yu+1].x-e[yu].x)/(double)(e[yu+1].t-v))));
        }
        cout<<ans<<endl;
    }

我们具体来讲一讲 ans 下面的一坨取 max 。 这个调整的监控信息出现在任何位置，影响答案的都只有这几个因素；

  1. AC 提交记录

    代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,t,id;
}e[100006];
struct node{
    int id,kl;
}ee[100006];
int n,m,po[100006],mo1[100006],mo2[100006];
bool cmp(Node a,Node b)
{
    return a.t<b.t;
}
bool cmp1(node a,node b)
{
    return a.kl>b.kl;
}
int find(int x)//改后时间 
{
    int l=1,r=n+1;
    while(l<r-1)
    {
        int mid=l+r>>1;
        if(e[mid].t<x)
        l=mid;
        else
        r=mid;
    }
    return r;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i].x>>e[i].t;
        e[i].id=i;
    }
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    po[e[i].id]=i;
    for(int i=2;i<=n;i++)
    {
        ee[i].kl=(int)(floor(abs(e[i].x-e[i-1].x)/(double)(e[i].t-e[i-1].t)));
        ee[i].id=i;
    }
    sort(ee+2,ee+1+n,cmp1);
    for(int i=2;i<=4;i++)
    mo1[ee[i].id]=i,mo2[ee[i].id-1]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v,ans;
        cin>>u>>v;
        int now=po[u];//排序后u点位置 
        int yu=find(v);//二分查找，寻找到第一个大于v时间的监控信息 
        if(mo1[now]==2||mo2[now]==2)// 如果now点对最大速度有影响 
        {
            if(mo1[now]==3 ||mo1[now]==3)// 如果now点对第二大速度还有影响 
            {
                ans=ee[4].kl;//选第三大速度 
            }
            else
            ans=ee[3].kl;//选第二大速度 
        }
        else
        ans=ee[2].kl;//选第一大速度 
        if(now!=yu)//当不在原位时 
        {
            if(yu>1)//当左边监控信息存在时 
            ans=max(ans,(int)(floor(abs(e[now].x-e[yu-1].x)/(double)(v-e[yu-1].t))));
            if(yu<=n)//当右边监控信息存在时 
            ans=max(ans,(int)(floor(abs(e[yu].x-e[now].x)/(double)(e[yu].t-v))));
            ans=max(ans,(int)(floor(abs(e[now+1].x-e[now-1].x)/(double)(e[now+1].t-e[now-1].t))));
        }
        else//当在原位时 
        {
            ans=max(ans,(int)(floor(abs(e[yu].x-e[yu-1].x)/(double)(v-e[yu-1].t))));
            ans=max(ans,(int)(floor(abs(e[yu+1].x-e[yu].x)/(double)(e[yu+1].t-v))));
        }
        cout<<ans<<endl;
    }
    return 0;
}

后记：

感谢 @Contingency_Core 和 @ lsc72 的hack。第一次写成功题解就被hack