[TIOJ 1403][HOJ 16] 超車問題 - EXTREME / 賽車

作法：

第一個要求的是超車的事件個數，這可以簡單的用BIT解決。而我們要能依序求出所有的超車事件，當然不可能把所有事件都算出來再排序。考慮任何時間點的超車事件，一定是相鄰的兩輛車前面追過後面，所以其實可以維護一個 linked list ，代表目前的車輛的前後情形，並且即將發生的超車事件只有 n-1 種可能，所以可以維護所有超車事件的 set ，每次都取出最小的就是這次發生的超車事件，然後要把 linked list 維護好， set 也會需要刪掉兩個東西( 如果有的話 )和加入新的有可能發生的超車事件。

code :

#include<bits/stdc++.h>
#define MOD 1000000
#define lowbit(x) (x&-x)
#define DB double
using namespace std;
const int maxn=250000+10 ;
const DB eps=1e-7 ;
 
int bit[200] ;
void add(int x)
{
    while(x<200) bit[x]++ , x+=lowbit(x) ;
}
 
int query(int x)
{
    int ret=0 ;
    while(x) ret+=bit[x] , x-=lowbit(x) ;
    return ret ;
}
 
int x[maxn],v[maxn] ;
int las[maxn],nex[maxn] ;
struct P
{
    int l,r ;
    DB t ;
    P(int _l,int _r)
    {
        l=_l ; r=_r ;
        t= ((DB)x[r]-x[l])/((DB)v[l]-v[r]) ;
    }
    bool operator < (const P &rhs) const
    {
        if(fabsl(t-rhs.t)>eps) return t<rhs.t ;
        return x[l]+t*v[l] < x[rhs.l]+rhs.t*v[rhs.l] ;
    }
};
 
set<P> st ;
void check(int l)
{
    int r=nex[l] ;
    if(!l || !r || v[r]>=v[l]) return ;
    st.insert(P(l,r)) ;
}
 
main()
{
    int n; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&v[i]) ;
    int ans=0 ;
    for(int i=n;i>=1;i--)
    {
        ans=(ans+query(v[i]-1))%MOD ;
        add(v[i]) ;
    }
    printf("%d\n",ans) ;
 
    for(int i=1;i<=n;i++)
        nex[i]= (i==n ? 0 : i+1), las[i]= i-1 ,
        check(i) ;
    int cnt=10000 ;
    while(!st.empty())
    {
        P u=*st.begin() ; st.erase(st.begin()) ;
        printf("%d %d\n",u.l,u.r) ;
        int L=las[u.l] , R=nex[u.r] ;
        st.erase(P(L,u.l)) ;
        st.erase(P(u.r,R)) ;
        las[u.r]=L ; nex[u.r]=u.l ;
        las[u.l]=u.r ; nex[u.l]=R ;
        nex[L]=u.r ; las[R]=u.l ;
        check(L) ; check(u.l) ;
        if(!(--cnt)) break ;
    }
}