Description
平面上有一个数轴,e点为目标点。 你现在要开♂车从w前往e,每移动1格需要1L油。 你的油箱容量为S,初始时装满了98#汽油。 数轴上有N个加油站,每个加油站提供98#,95#,92#中的一种。 到了加油站你可以选择加任意数量的油,你的油箱是兹瓷所有油甚至混合油的。。 你认为98#最吼,95#其次,92#跑的最慢。 于是你钦点使消耗的92#最少。 如果有多种方案,使95#最少。 M次询问。 N,M<=2*1e5, 0<坐标<1e9,且起点的坐标
Solution
一道很吼的题。 首先,你可以意识到,你只需要向右走,因为向左走无意义地消耗汽油。 然后,对于当前你所到达的加油站,你需要找出他下一个需要去到的加油站。 很显然,我们需要到达离他最近的油品大于等于他的加油站。 如果没有,那么我们就跑油品尽量好且尽量远的加油站。 并且我们可以让需要用的油减少,因为可行区间有重叠部分。 具体实现见代码(懒癌晚期) 然后,你知道了贪心规则,就可以开一个队列记录当前加油站能到达的各种油品的点。 F[i][0/1]表示从i这个加油站空油箱走到e所需要的最少92#,95#。 然后就可以转移了。 细节有(fei)点(change)多。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,
a,b) for(int i=
a
#define fd(i,
a,b) for(int i=
a
#define N
200005
using namespace std
struct note{int ty,x,id
bool cmp(note x,note y) {
return x.x<y.x||x.x==y.x&&x.ty<y.ty
int n,m,e,s,tot,k,x,l[
4],r[
4],d[
4][N*
2],f[N*
2][
2],ans[N][
2]
int main() {
scanf(
"%d%d%d%d",&e,&s,&n,&m)
fo(i,
1,n) scanf(
"%d%d",&
a[i].ty,&
a[i].x)
tot=n
fo(i,
1,m) scanf(
"%d",&x),
a[++tot].ty=
4,
a[tot].x=x,
a[tot].id=i
sort(
a+
1,
a+tot+
1,cmp)
fo(i,
1,tot)
if (
a[i].ty==
3&&
a[i].x==e) {k=i
l[
1]=l[
2]=l[
3]=
1
fd(i,k-
1,
1) {
fo(j,
1,
3)
while (l[j]<=r[j]&&
a[d[j][l[j]]].x-
a[i].x>s) l[j]++
int cnt=
0
a[d[cnt][r[cnt]]].x>
a[d[j][r[j]]].x)) cnt=j
if (cnt) {
fo(j,
0,
1) f[i][j]=f[d[cnt][r[cnt]]][j]
if (
a[i].ty<
3) f[i][
a[i].ty-
1]+=
a[d[cnt][r[cnt]]].x-
a[i].x
}
else {
int bz=
0
fd(j,
3,
1)
if (l[j]<=r[j]) {bz=j
if (!bz) {fo(j,
1,i) f[j][
0]=f[j][
1]=-
1
fo(j,
0,
1) f[i][j]=f[d[bz][l[bz]]][j]
if (
a[i].ty<
3) f[i][
a[i].ty-
1]+=s
f[i][
a[d[bz][l[bz]]].ty-
1]-=s-
a[d[bz][l[bz]]].x+
a[i].x
}
if (
a[i].ty!=
4) d[
a[i].ty][++r[
a[i].ty]]=i
}
fo(i,
1,k) fo(j,
0,
1) ans[
a[i].id][j]=f[i][j]
fo(i,
1,m) printf(
"%d %d\n",ans[i][
0],ans[i][
1])
}
转载请注明原文地址: https://ju.6miu.com/read-1295875.html