2021上海省赛 H. 鸡哥的 AI 驾驶（非二分做法）

考虑对车双关键字排序，第一关键字为坐标，第二关键字为速度。
排序后，只有前后不同类型车辆可以碰撞，在相同坐标的车已经按照速度排序的情况下，让每辆车指向前一辆和后一辆型号不同的车，一定能覆盖所有会碰撞的车。所以正负分别跑一遍取最小值就可以了（注意特判碰撞时间是否为整数，如果为整数则-1）。

代码：

#include
using namespace std;
#define int long long
const int N = 1e6+10;
int nex[N],pre[N];
struct node{
    int p,v,t;
}a[N];
int n,k,last;
bool cmp(node a,node b){
    if(a.p==b.p)return a.v < b.v;
    return a.p < b.p;
}
signed main(){
    cin >> n >> k;
    for(int i = 0 ; i < n ; i ++ )cin >> a[i].p >> a[i].v >> a[i].t;
    sort(a,a+n,cmp);
    last = 0;
    pre[last] = last;
    for(int i = 1 ; i < n ; i ++ ){
        if(a[i].t!=a[i-1].t)last = i-1;
        pre[i] = last;
    }
    last = n-1;
    nex[last] = last;
    for(int i = n-2 ; i >= 0 ; i -- ){
        if(a[i].t!=a[i+1].t)last = i+1;
        nex[i] = last;
    }
    int ans = 1e10;
    for(int i = 0 ; i < n ; i ++ ){
        if(a[nex[i]].t!=a[i].t){
            if(a[i].v - a[nex[i]].v > 0){
                if((a[nex[i]].p - a[i].p)%(a[i].v-a[nex[i]].v)==0){
                    ans = min(ans,(a[nex[i]].p - a[i].p)/(a[i].v-a[nex[i]].v)-1);    
                }
                else ans = min(ans,(a[nex[i]].p - a[i].p)/(a[i].v-a[nex[i]].v));
            }
        }
    }
    for(int i = n-1 ; i >= 0 ; i -- ){
        if(a[pre[i]].t!=a[i].t){
            if(a[pre[i]].v - a[i].v > 0){
                if((a[i].p-a[pre[i]].p)%(a[pre[i]].v-a[i].v)==0){
                    ans = min(ans,(a[i].p-a[pre[i]].p)/(a[pre[i]].v-a[i].v)-1);    
                }
                else ans = min(ans,(a[i].p-a[pre[i]].p)/(a[pre[i]].v-a[i].v));
            }
        }
    }
    if(ans==1e10)cout<<-1<<'n';
    else cout << ans << 'n';
    return 0;
}