題目鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=6136

題解

完了，普及題都不會做了。。。

發(fā)現(xiàn)一個重要性質(zhì)是只有相鄰的人才會相撞，于是直接拿堆維護即可。。。

WA了好幾發(fā)。。。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<algorithm> #define llong long long using namespace std;const int N = 1e5; struct Fraction {llong x,y;Fraction() {}Fraction(llong _x,llong _y) {x = _x,y = _y;}void output() {printf("%lld/%lld ",x,y);}bool operator <(const Fraction &arg) const{return x*arg.y<y*arg.x;} }; struct Element {llong a,b; int id;bool operator <(const Element &arg) const{return b<arg.b;} } a[N+3]; struct Node {int id1,id2; Fraction x;Node() {}Node(int _id1,int _id2,Fraction _x) {id1 = _id1,id2 = _id2,x = _x;}bool operator <(const Node &arg) const{return arg.x<x;} }; priority_queue<Node> que; bool vis[N+3]; int nxt[N+3],prv[N+3]; int n; llong m;llong gcd(llong x,llong y) {return y==0 ? x : gcd(y,x%y);}Fraction calc(Element x,Element y) {if(x.a<y.a) {swap(x,y);}if(x.b>y.b) {y.b += m;}return Fraction(y.b-x.b,x.a-y.a); }int main() {int T; scanf("%d",&T);while(T--){scanf("%d%lld",&n,&m);for(int i=1; i<=n; i++) scanf("%lld",&a[i].b);for(int i=1; i<=n; i++) scanf("%lld",&a[i].a),a[i].id = i;sort(a+1,a+n+1);for(int i=1; i<=n; i++) prv[i] = i==1?n:i-1,nxt[i] = i==n?1:i+1;for(int i=1; i<=n; i++) que.push(Node(i,nxt[i],calc(a[i],a[nxt[i]])));Fraction ans;while(!que.empty()){Node cur = que.top(); que.pop();int u = cur.id1,v = cur.id2;if(vis[u]||vis[v]) continue;ans = cur.x;if(a[u].id>a[nxt[u]].id) swap(u,v);vis[u] = true;if(prv[u]!=nxt[u]){que.push(Node(prv[u],nxt[u],calc(a[prv[u]],a[nxt[u]])));}nxt[prv[u]] = nxt[u];prv[nxt[u]] = prv[u];}llong g = gcd(ans.x,ans.y);printf("%lld/%lld\n",ans.x/g,ans.y/g);for(int i=1; i<=n; i++) vis[i] = nxt[i] = prv[i] = 0;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 6136 Death Podracing (堆)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。