题目链接：https://nanti.jisuanke.com/t/15772
解析：一个核心部门a位于楼L（高h1）到其他核心部门b位于楼R（高h2），求L~R的最小的高度h，然后最短路径为abs(R-L)+abs(h-h1)+abs(h-h2)，关键问题就是一个RMQ
代码：
#include<bits/stdc++.h> #define N 200009 using namespace std; int a[N], dp[N][33]; struct node { int x, y; }p[N]; bool cmp(node a, node b) { return a.x < b.x; } void RMQ(int n) { for(int j = 1; j != 20; j++) { for(int i = 1; i <= n; i++) { if(i + (1<<j) - 1 <= n) dp[i][j] = min(dp[i][j-1], dp[i+(1<<j>>1)][j-1]); } } } int main() { int n, k, m, l, r; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); dp[i][0] = a[i]; } RMQ(n); scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d%d", &p[i].x, &p[i].y); } sort(p + 1, p + m + 1, cmp); int ans = 0; for(int i = 1; i <= m; i++) { l = p[i].x; for(int j = i + 1; j <= m; j++) { r = p[j].x; int kk = (int)(log(1.0*r-l+1) / log(2.0)); int h = min(dp[l][kk], dp[r-(1<<kk)+1][kk]); h = min(h, min(p[i].y, p[j].y)); int sum = abs(p[i].y - h) + abs(p[j].y - h); sum += abs(r - l); if(sum <= k) ans++; } } printf("%d\n", ans); return 0; }
