c/c++语言开发共享洛谷P1081 开车旅行(倍增)

题意

题目链接

sol

咕了一年的题解。。

并不算是很难，只是代码有点毒瘤

(f[i][j])表示从(i)号节点出发走了(2^j)轮后总的距离

(da[i][j])同理表示(a)的距离,(db[i][j])与(da)同理

倍增优化一下

注意最后(a)可能还会走一次

#include<bits/stdc++.h> #define pair pair<int, int> #define mp make_pair #define fi first #define se second  #define fin(x) {freopen(#x".in","r",stdin);} #define pb(x) push_back(x) #define ll long long  //#define int long long  using namespace std; const int maxn = 1e5 + 10; ll inf = 2e9 + 10, b = 20; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, jp[maxn][21], nxa[maxn], nxb[maxn], flag[maxn], h[maxn]; ll f[maxn][21], da[maxn][21], db[maxn][21]; struct node {     ll hi, id;     bool operator < (const node &rhs) const{         return hi == rhs.hi ? h[id] < h[rhs.id] : hi < rhs.hi;     } }; int get(int x, int y) {     return abs(h[x] - h[y]); } set<node> s; void pre() {     s.insert((node) {-inf * 2, 0}); s.insert((node) {inf * 2, 0});     s.insert((node) {-inf * 2 + 1, 0}); s.insert((node) {inf * 2 + 1, 0});     s.insert((node) {h[n], n});     memset(f, 0x3f, sizeof(f));     for(int i = n - 1; i >= 1; i--) {         set<node> :: iterator y = s.lower_bound((node) {h[i], i});         vector<node> tmp; tmp.clear();         tmp.push_back((node) {get(y -> id, i), y -> id}); y++;         tmp.push_back((node) {get(y -> id, i), y -> id}); y--; y--;         tmp.push_back((node) {get(y -> id, i), y -> id}); y--;         tmp.push_back((node) {get(y -> id, i), y -> id});         sort(tmp.begin(), tmp.end());         nxa[i] = tmp[1].id;         nxb[i] = tmp[0].id;         s.insert((node) {h[i], i});         if(tmp[1].id != 0 && tmp[0].id != 0) f[i][0] = tmp[1].hi + db[tmp[1].id][0];         jp[i][0] = nxb[nxa[i]];         da[i][0] = get(i, nxa[i]);         db[i][0] = get(i, nxb[i]);     }     for(int j = 1; j <= b; j++)          for(int i = 1; i <= n; i++) {             if(jp[i][j - 1])                  jp[i][j] = jp[jp[i][j - 1]][j - 1],                  f[i][j] = f[i][j - 1] + f[jp[i][j - 1]][j - 1],                 da[i][j] = f[i][j] == inf ? 0 : da[i][j - 1] + da[jp[i][j - 1]][j - 1];              }  } void print() {     for(int i = 1; i <= n; i++) printf("**%dn", f[i][0]); } pair query(int pos, int val) {     ll a1 = 0, a2 = 0;     for(int i = b; ~i; i--)          if(f[pos][i] <= val)              val -= f[pos][i], a1 += da[pos][i], a2 += f[pos][i] - da[pos][i], pos = jp[pos][i];     if(da[pos][0] <= val) a1 += da[pos][0];     return mp(a1, a2);    } signed main() {    // freopen("drive3.in", "r", stdin);  //   freopen("a.out", "w", stdout);     n = read();     for(int i = 1; i <= n; i++) h[i] = read(); h[0] = inf;      pre();    // print();     int x0 = read(), ans = n;     double tmp = 1e22;      for(int i = 1; i <= n; i++) {         pair now = query(i, x0);         if(now.se == 0) continue;         if((double)now.fi / now.se < tmp) tmp = (double)now.fi / now.se, ans = i;      }     printf("%dn", ans);     int m = read();     while(m--) {         int si = read(), mi = read();         pair now = query(si, mi);         printf("%d %dn", now.fi, now.se);     }     return 0; }