杭电多校第一场 1004Vacation(数学/动态规划)

vacation

vacation题解

题目意思就是
你现在在一条单行道上
然后你前边有n辆车
已知所有车距离红绿灯的距离s，速度v，车长l
假设大家车技都很好
距离可以保持为0
那么问你需要多久才能到红绿灯那

上面的博写的是O(n)的复杂度
从末态起手
很精妙

然后看懂了题解的小根堆维护
如果用O(nlogn)就像是常规的动态规划了

7.26更新

首先我们把各辆车与前一辆车相距为0的时间求出来
用这个来不断让我们自己的车逼近前一辆车
然后其他的车也都会逼近前一辆车
并且用并查集来联通已经逼近的车
这个情况下又会产生新的状态
我们有t数组和d数组来维护当前时间的当前距离
接着所有的车不断接近前一辆车
知道所有车连在一起
或者说
车在接近过程中我们的车已经开到了终点
那么就可以得出答案了

一个用数学方法是简单题
一个用动态规划就是中等题了。。。

emmm
今儿注释了一下

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn=2e5+5;

struct DR{
  int id;
  double nt;
  bool operator > (const DR &Vt)const{
    return nt>Vt.nt;
  }
};

priority_queue<DR,vector<DR>,greater<DR> > sq;//小根堆，会以小的nt优先 

bool vis[maxn];
double d[maxn],t[maxn];
int l[maxn],s[maxn],v[maxn];
int f[maxn],sl[maxn];
int n;

int Find(int x){
  return f[x]==x?x:f[x]=Find(f[x]);//并查集一行写法 
}

int main(){
  ios::sync_with_stdio(false);
  while( cin >> n ){
    for(int i=0;i<=n;++i) cin >> l[i] ;
    for(int i=0;i<=n;++i) cin >> s[i] ;
    for(int i=0;i<=n;++i) cin >> v[i] ;
    for(int i=0;i<=n;++i) sl[i]=i;
    for(int i=0;i<=n;++i) f[i]=i;
    for(int i=0;i<=n;++i) vis[i]=false;
    for(int i=0;i<=n;++i) t[i]=0;
    for(int i=0;i<n;++i) d[i]=s[i]-s[i+1]-l[i+1];//求出间隙 
    for(int i=0;i<n;++i){
      if( v[i]>v[i+1] ){
        sq.push(DR{i,d[i]/(v[i]-v[i+1])});//压入一个id为i，追上前一辆车的时间的状态 
      }
    }
    double cd=0,cv=v[0],ct=0; 
    while( !sq.empty() ){
      DR tp=sq.top();sq.pop();
      if( vis[tp.id] ) continue;
      vis[tp.id]=true;
      if( cd+cv*(tp.nt-ct)>=s[0] ){//如果已经能够到达终点 
        ct+=(s[0]-cd)/cv;//就让他走完 
        cd=s[0];//当前路程直接到达 
        break;
      }
      cd+=cv*(tp.nt-ct);//更新当前0车走的路程 
      ct=tp.nt;//当前时间更新 
      int p=tp.id;
      f[p]=Find(p+1);//p与p+1连在一起 （连右边 
      if( sl[p]==0 ) cv=v[f[p]];//如果左连到了0的车，那么速度就降为所连右边车的速度 
      sl[Find(p+1)]=sl[p];//连左边 
      d[sl[p]-1]-=(v[sl[p]-1]-v[p])*(tp.nt-t[sl[p]-1]);//更新  后一辆车  的d 
      t[sl[p]-1]=tp.nt;//更新后一辆车的t 
      if( v[sl[p]-1]>v[f[p]] )//如果后一辆车速度比前面连在一起的车速度大 
        sq.push(DR{sl[p]-1,d[sl[p]-1]/( v[sl[p]-1]-v[f[p]] )+tp.nt});//压入一个更新后的状态 
    }
    while( !sq.empty() ) sq.pop();//清空栈 
    //如果全挤在一起 还不能到终点 
    if( cd!=s[0] ) ct+=(s[0]-cd)/cv;
    cout << fixed << setprecision(10) << ct << endl ;
  }
  return 0;
}
/*
1
1 1
100 50
100 1

2
1 1 1
100 99 50
100 2 1
*/