星际飞船竞赛题解

一、题目分析

题目描述了一个星际飞船竞赛场景，每艘飞船以固定速度巡航，起始位置不同。需要计算飞船之间的超越次数，并按时间顺序输出前10000次超越。关键要点如下：

1. 输入条件：

   • 飞船按起始位置升序排列（X₁ < X₂ < ... < Xₙ）。
   • 每艘飞船速度恒定，且起始位置唯一。
   • 任意时刻同一位置最多有两艘飞船。

2. 输出要求：

   • 总超越次数对1000000取模。
   • 按时间顺序输出前10000次超越（时间相同则按位置排序）。

3. 核心问题：

   • 计算超越次数（逆序对问题）。
   • 动态维护飞船位置关系，预测后续超越。

二、算法思路

1. 总超越次数计算：

   • 使用归并排序计算速度序列中的逆序对数目（若i < j且Vᵢ > Vⱼ，则飞船i最终会超越飞船j）。

2. 超越事件模拟：

   • 使用双向链表维护飞船的相对位置。
   • 初始时，仅相邻飞船可能发生超越，将这些事件加入优先队列（按时间和位置排序）。
   • 每次取出最早的超越事件，更新链表结构，并检查新形成的相邻对是否会发生超越。

三、代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=250000,tt=1000000;

struct Car
{
    int x,v;
    bool operator <= (const Car &a) const {return v<=a.v;}
}; //赛车的结构体
struct Heap
{
    int x,y;
    double ti,dis;
    bool operator < (const Heap &a) const {return ti<a.ti||ti==a.ti&&dis<a.dis;}
}; //堆的结构体
int n,len_s,ans,l[maxn+5],r[maxn+5]; //l[i]表示i的左边，r[i]表示i的右边
Car a[maxn+5],b[maxn+5],c[maxn+5];
Heap heap_s[maxn+10000+5]; //因为最多做10000次，每次最多会增加一个，所以要开maxn+10000

bool Eoln(char ch) {return ch==10||ch==13||ch==EOF;}
int readi(int &x) //读入优化
{
    int tot=0,f=1;
    char ch=getchar();if (ch==EOF) return EOF;
    while ('9'<ch||ch<'0') {if (ch=='-') f=-f;ch=getchar();}
    while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
void msort(int L,int R) //二路归并
{
    if (L>=R) return;int mid=L+(R-L>>1);
    msort(L,mid);msort(mid+1,R);
    for (int k=L;k<=R;k++) c[k]=b[k];
    int i=L,j=mid+1;
    for (int k=L;k<=R;k++)
        if (j>R||i<=mid&&c[i]<=c[j]) b[k]=c[i++]; else
        b[k]=c[j++],ans=(ans+mid-i+1)%tt;
}
void put_s(int x,int y,double ti,double dis) //放入堆中
{
    int son;heap_s[++len_s]=(Heap){x,y,ti,dis};son=len_s;
    while (son!=1&&heap_s[son]<heap_s[son>>1])
    {
        swap(heap_s[son],heap_s[son>>1]);
        son>>=1;
    }
}
void del_s() //删除堆顶
{
    int fa=1,son;heap_s[1]=heap_s[len_s--];
    while (2*fa<=len_s)
    {
        if (2*fa+1>len_s||heap_s[2*fa]<heap_s[2*fa+1]) son=2*fa; else son=2*fa+1;
        if (heap_s[son]<heap_s[fa])
        {
            swap(heap_s[son],heap_s[fa]);
            fa=son;
        } else break;
    }
}
double getti(int i,int j) {return (double)(a[j].x-a[i].x)/(a[i].v-a[j].v);} //得到i和j相遇的时间
double getdis(int i,int j) {return a[i].x+getti(i,j)*a[i].v;} //得到i和j相遇的位置
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);
    for (int i=1;i<=n;i++) readi(a[i].x),readi(a[i].v);
    memcpy(b,a,sizeof(b)); //备份一个b用来二路归并求逆序对
    msort(1,n);
    printf("%d\n",ans);
    for (int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1;
    for (int i=1;i<=n-1;i++) if (a[i].v>a[i+1].v)
        put_s(i,i+1,getti(i,i+1),getdis(i,i+1)); //相邻建边，加入堆中
    int te=1;
    while (len_s&&te<=10000)
    {
        int x=heap_s[1].x,y=heap_s[1].y,lx=l[x],ry=r[y];del_s(); //得到堆顶
        if (r[x]!=y||l[y]!=x) continue; //判断该堆顶是否“过期”，也就是判重
        printf("%d %d\n",x,y);te++;
        if (ry!=n+1) {l[ry]=x;if (a[x].v>a[ry].v) put_s(x,ry,getti(x,ry),getdis(x,ry));} //x和y交换过后，x和r[y]产生新状况
        if (lx) {r[lx]=y;if (a[lx].v>a[y].v) put_s(lx,y,getti(lx,y),getdis(lx,y));} //x和y交换后，y和l[x]产生新状况
        l[x]=y;r[y]=x;r[x]=ry;l[y]=lx; //修正链表
    }
    return 0;
}

四、代码解释

1. 归并排序计算逆序对：

   • msort函数通过归并排序统计速度序列中的逆序对数目，对应总超越次数。

2. 双向链表维护位置关系：

   • l[i]和r[i]分别表示飞船i的前驱和后继。
   • 初始时按起始位置升序排列，仅相邻飞船可能初始时发生超越。

3. 优先队列处理超越事件：

   • Heap结构体存储超越事件（时间、位置、涉及飞船）。
   • put_s和del_s函数维护最小堆，确保最早发生的事件优先处理。

4. 事件处理流程：

   • 取出堆顶事件，检查是否有效（未被其他事件影响）。
   • 输出超越事件，更新链表结构，检查新相邻对是否会发生超越并加入堆。

五、复杂度分析

• 时间复杂度：

  • 归并排序计算逆序对：O(N log N)。
  • 处理超越事件：O(N + K log N)，其中K为实际输出的超越次数（最多10000）。

• 空间复杂度：

  • 双向链表和堆：O(N)。

六、关键技巧

1. 动态维护：利用双向链表高效处理飞船位置关系的变化。
2. 事件驱动：通过优先队列按时间顺序处理超越事件，确保输出顺序正确。
3. 剪枝优化：仅当相邻飞船速度满足条件时才加入事件队列，避免无效计算。

该算法通过结合归并排序和优先队列，巧妙地解决了动态超越事件的预测问题，确保在大规模数据下仍能高效运行。