Keith买了一辆新车，打算把自己的新车开到学校，给403的小伙伴们看看。 Keith家（多个）在城区，从城区到学校的路可以抽象成一个数轴，Keith家的坐标为W，学校的坐标为E。路上有很多加油站，每个加油站能提供92#，95#，98#三种汽油中的一种。由于Keith不缺钱，每到一个加油站，他都能加任意多的油。由于道路是双向的，Keith的车既能往左开，也能往右开。 1升汽油可以跑1千米，这与油的种类无关。车的油箱容量是S升，任何时候油箱中的油都不能超过S升，但是作为Keith大神的御用座驾，这台车有点与众不同，它的油箱中能同时存在多种汽油。出发时，油箱是装满98#汽油的。 众所周知的是，98#汽油最好，92#最差。由于Keith很爱惜自己的新车，所以他希望用尽可能少的92#汽油，如果有多种可能用的92#同样多，那就要求用的95#尽可能少。 现在Keith告诉你N个家的坐标Wi，学校的坐标E，以及路上所有加油站的坐标，求从各个家分别到学校的最优策略中，需要消耗的最少92#和95#汽油。 由于Keith忙于研究SAM及其相关应用，所以他找到你来帮他完成这个任务。
学校看做98加油站。 设f[i][0/1/2]表示在第i个加油站，只通过（（92加油站）95加油站）98加油站还需要多少的油才能到终点。 转移很容易，为了方便找到下一个符合要求的点可以开三个vector，每次在vector里二分，由于学校在最右边而且是98加油站所以一定能找到。 求答案的话，如果f[0]大于0说明无解，否则最少花费的92油为f[1]，最少花费的95油为f[2]-f[1]
#include<cstdio> #include<algorithm> #include<vector> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; typedef long long ll; const int maxn=200000+10; struct dong{ int x,y,id; friend bool operator <(dong a,dong b){ return a.x<b.x; } } d[maxn],zlt; vector <dong> a,b,c; int f[maxn][3]; int i,j,k,l,r,t,n,m,top,e,s; int main(){ scanf("%d%d%d%d",&e,&s,&n,&m); fo(i,1,n) scanf("%d%d",&d[i].y,&d[i].x); d[n+1].x=e; d[n+1].y=3; sort(d+1,d+n+2); fd(i,n+1,1) if (d[i].x==e&&d[i].y==3) break; top=i; fo(i,1,top){ d[i].id=i; if (d[i].y==3){ a.push_back(d[i]); b.push_back(d[i]); c.push_back(d[i]); } else if (d[i].y==2){ a.push_back(d[i]); b.push_back(d[i]); } else a.push_back(d[i]); } fd(i,top-1,1){ j=(*(upper_bound(a.begin(),a.end(),d[i]))).id; f[i][0]=f[j][0]+max(d[j].x-d[i].x-s,0); if (d[i].y>1){ j=(*(upper_bound(b.begin(),b.end(),d[i]))).id; f[i][1]=f[j][1]+max(d[j].x-d[i].x-s,0); if (d[i].y==3){ j=(*(upper_bound(c.begin(),c.end(),d[i]))).id; f[i][2]=f[j][2]+max(d[j].x-d[i].x-s,0); } } } fo(i,1,m){ scanf("%d",&j); zlt.x=j; t=(*(upper_bound(a.begin(),a.end(),zlt))).id; k=f[t][0]+max(d[t].x-j-s,0); if (k>0) printf("-1 -1\n"); else{ t=(*(upper_bound(b.begin(),b.end(),zlt))).id; l=f[t][1]+max(d[t].x-j-s,0); printf("%d ",l); t=(*(upper_bound(c.begin(),c.end(),zlt))).id; r=f[t][2]+max(d[t].x-j-s,0); printf("%d\n",r-l); } } }