【题解】【HDU6136】2017多校第8场 炮艇大赛之正式赛

用了个比较显然的做法

思路：

第一次相遇的必是两个环上相邻的两个人

正确性显然

第一个出局的人不会对后续的状态有任何影响

同上，显然

于是我们就把问题的规模从n缩小到了n-1

对于缩小后的子问题，我们也能用同样的方法

但同时，原本不相邻的现在相邻了

于是我们需要一种方法，来快速取得最小值，并支持插入

很显然，这就是堆

搞定了……

时间复杂度(O(nlogn))

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N=100010;

struct note {
    int x,y;
    note(int u=0,int v=1){
        x=u;
        y=v;
    }
};

bool operator < (const note &x,const note &y) {
    return x.x/(double)x.y>y.x/(double)y.y;
}

note operator + (const note &x,const note &y) {
    return note(x.x*y.y+y.x*x.y,x.y*y.y);
}

note operator - (const note &x,const note &y) {
    return note(x.x*y.y-y.x*x.y,x.y*y.y);
}

struct data {
    int x,y;
    note t;
};

bool operator < (const data &a,const data &b) {
    return a.t<b.t;
}

struct boat {
    int d;
    int v;
    int val;
};

bool operator < (const boat &x,const boat &y) {
    return x.d<y.d;
}

int n,L;
note ans;
data e;
boat a[N];
priority_queue<data> q;
bool out[N];

note get(boat x,boat y) {
    if (x.d<y.d) {
        if (x.v<y.v) {
            return note(L-y.d+x.d,y.v-x.v);
        } else {
            return note(y.d-x.d,x.v-y.v);
        }
    } else {
        if (x.v<y.v) {
            return note(x.d-y.d,y.v-x.v);
        } else {
            return note(L-x.d+y.d,x.v-y.v);
        }
    }
}

inline int gcd(int x,int y) {
    while(y^=x^=y^=x%=y);
    return x;
}

inline bool comp(const boat &x,const boat &y) {
    return x.d<y.d;
}

int main() {
    scanf("%d %d",&n,&L);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i].d);
        a[i].val=i;
    }
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i].v);
    }
    sort(a+1,a+n+1,comp);
    e.x=n;
    e.y=1;
    e.t=get(a[1],a[n]);
    q.push(e);
    for(int i=1;i<n;i++) {
        e.x=i;
        e.y=i+1;
        e.t=get(a[i],a[i+1]);
        q.push(e);
    }
    int num=n;
    while(q.size()>1) {
        e=q.top();
        q.pop();
        if (out[a[e.x].val]||out[a[e.y].val]) {
            continue;
        }
        if (num==2) {
            break;
        }
        if (a[e.x].val<a[e.y].val) {
            out[a[e.x].val]=1;
            while(out[a[e.x].val]) {
                e.x--;
                if (e.x==0) {
                    e.x=n;
                }
            }
        } else {
            out[a[e.y].val]=1;
            while(out[a[e.y].val]) {
                e.y++;
                if (e.y>n) {
                    e.y=1;
                }
            }
        }
        num--;
        e.t=get(a[e.x],a[e.y]);
        q.push(e);
    }
    data k=q.top();
    ans=k.t;
    int o=gcd(ans.x,ans.y);
    printf("%d/%d",ans.x/o,ans.y/o);
    return 0;
}