当前位置：首页 > news >正文

开车，开车！！！

news 2024/5/20 2:13:38

倍增问题

其实说实话，我现在也不知道倍增问题是什么东西！

题目链接：
P1081 开车旅行

标成如下：

#include<bits/stdc++.h>
#define LL long long 
#define N 100005         //小A开山蹦蹦，小B很正常 0是B 1是A 
using namespace std;
struct sd{int num,high;bool operator < (const sd njc) const{return high<njc.high;}
}city[N];
set<sd> s;//定义集合set方便后面排序用。 
set<sd> ::iterator it;//说白了就是一个指针 
int goal[N][2],dis[N][2];//分别定义的是N的目标点和N到目标点的距离 
int loc[N][25], f[N][25][2];//分别存的是 loc从i号点（i<=n）经过2^j的操作到达点的位置（首先存的是一轮）（从goal传入） //f代表从第i个点（i<=N）经过2^j的操作到达点的距离（从dis传入）
void update(sd x,sd y)
{if(!goal[x.num][0]){goal[x.num][0]=y.num;dis[x.num][0]=abs(x.high-y.high);}else if(abs(x.high-y.high)<dis[x.num][0]||(abs(x.high-y.high)==dis[x.num][0]&&y.high<city[goal[x.num][0]].high)){//如果现在两个的差小于原来的差 或者 相等但是现在的海拔要低一些那么见下面操作 goal[x.num][1]=goal[x.num][0];dis[x.num][1]=dis[x.num][0];goal[x.num][0]=y.num;dis[x.num][0]=abs(x.high-y.high);}else if(abs(x.high-y.high)<dis[x.num][1]||(abs(x.high-y.high)==dis[x.num][1]&&y.high<city[goal[x.num][1]].high)){//importantgoal[x.num][1]=y.num;dis[x.num][1]=abs(x.high-y.high);}else if(!goal[x.num][1]){goal[x.num][1]=y.num;dis[x.num][1]=abs(x.high-y.high);}
}
void query(int i,int x,LL &dista,LL &distb)
{for(int j=20;j>=0;--j){if(f[i][j][0]+f[i][j][1]<=x&&loc[i][j]){dista+=f[i][j][0];distb+=f[i][j][1];x-=(f[i][j][0]+f[i][j][1]);i=loc[i][j];}}if(goal[i][1]&&dis[i][1]<=x)//important 这里的1指的是A，这里在判断最后A是否还可以开车 {dista+=dis[i][1];}
}
int main()
{int n;cin>>n;//读入for(int i=1;i<=n;i++){scanf("%d",&city[i].high);city[i].num=i;} for(int i=n;i>=1;i--)//预处理操作 {s.insert(city[i]);it=s.find(city[i]);if(it!=s.begin()){it--;update(city[i],*it);if(it!=s.begin()){it--;update(city[i],*it);it++;}it++;}if((++it)!=s.end()){update(city[i],*it);if((++it)!=s.end())update(city[i],*it);it--;}it--;}for(int i=1;i<=n;i++){loc[i][0]=goal[goal[i][1]][0];//每一轮开车开完后到达的位置 （A，B算一轮） f[i][0][0]=dis[i][1]; f[i][0][1]=dis[goal[i][1]][0];}for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){loc[i][j]=loc[loc[i][j-1]][j-1];f[i][j][0]=f[i][j-1][0]+f[loc[i][j-1]][j-1][0];f[i][j][1]=f[i][j-1][1]+f[loc[i][j-1]][j-1][1];}}int limit;//下面开始解决题目中的第一个问题！！！ cin>>limit;LL a=1e5;LL b=0;int began=0;for(int i=1;i<=n;i++){LL dista=0, distb=0;query(i,limit,dista,distb);if(distb&&(distb*a>dista*b)){began=i;a=dista;b=distb;}} //printf("%lld\n",began)cout<<began<<endl;int m;cin>>m;//下面的代码解决题目中的第二个问题 for(int i=1;i<=m;++i){LL dista=0,distb=0;int s,x;scanf("%d%d",&s,&x);query(s,x,dista,distb);printf("%lld %lld\n",dista,distb);//cout<<dista<<' '<<distb<<endl;}return 0;
}