Main » 2013 October 23 » [模拟赛NOIP2010]碰碰车
8:58 AM [模拟赛NOIP2010]碰碰车 |
哈哈，原来水题一道碰撞时交换速度，就不用考虑车之间的碰撞了，只要考虑一下和挡板的碰撞就行了，用堆维护碰撞时间。std::priority_queue是个不错的选择.#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 100010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int n,m,k; struct node { double t,v;int d; bool operator<(const node A)const { return t>A.t; } }; int times[N]; priority_queue<node> heap; int main() { scanf("%d%d%d",&n,&m,&k); double tv;int td,tp,i; FOR(i,1,n) { scanf("%lf%d%d",&tv,&td,&tp); node tmp; if (td==-1) tmp.d=0;else tmp.d=1; tmp.v=tv;tmp.t=(double)(fabs(tp-tmp.d*m))/tv; heap.push(tmp); } times[0]=times[1]=k; double ans; while (heap.size()) { node Top=heap.top(); heap.pop(); if (times[Top.d]==0) ans=Top.t; else { times[Top.d]--; node tmp=Top; tmp.d=1-tmp.d; tmp.t+=(double)m/tmp.v; heap.push(tmp); } } printf("%.2f\n",ans); } |
|
|
| Total comments: 0 | |