题目链接：https://nanti.jisuanke.com/t/15772
题意：中文题诶～
思路：对于坐标为p1(x1, y1), p2(x2, y2) 的两个核心, 其中 x1 <= x2 用 d(p1, p2) 表示两者间最矮的大楼，则需要时间为：
对于d(p1, p2) >= min(y1, y2)情况，cnt = abs(x2 - x1) + abs(y2 - y1)
对于d(p1, p2) < min(y1, y2)情况，cnt = y1 + y2 - 2*d(p1, p2) + abs(x2 -x1)
所以对于中等难度，可以枚举所有核心组合的情况，对于当前情况，若 cnt <= k，则计数加一；
那么现在问题为求 d，可以用 dis[i][j] 存储前 i 个元素 j 出现的次数，那么只需要枚举 h 即可得到 d(p1, p2)，而 h <= 20，显然是可行的．．．
代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <algorithm> 5 #include <string.h> 6 using namespace std; 7 8 const int MAXN = 2e5 + 10; 9 int a[MAXN], x[MAXN], y[MAXN], dis[MAXN][30]; 10 11 int main(void){ 12 int n, k, m; 13 scanf("%d%d", &n, &k); 14 for(int i = 1; i <= n; i ++){ 15 scanf("%d", &a[i]); 16 for(int j = 1; j <= 20; j ++){ 17 if(j == a[i]) dis[i][j] = dis[i - 1][j] + 1; 18 else dis[i][j] = dis[i - 1][j]; 19 } 20 } 21 scanf("%d", &m); 22 for(int i = 0; i < m; i ++){ 23 scanf("%d%d", &x[i], &y[i]); 24 } 25 int ans = 0; 26 for(int i = 0; i < m; i++){ 27 for(int j = i + 1; j < m; j++){ 28 int cnt1 = x[i], cnt2 = x[j]; 29 if(cnt1 > cnt2){ 30 int cc = cnt1; 31 cnt1 = cnt2; 32 cnt2 = cc; 33 } 34 if(cnt1 == cnt2){ 35 if(abs(y[i] - y[j]) <= k) ans++; 36 }else{ 37 int d; 38 int cc = min(y[i], y[j]); 39 for(d = 1; d <= 20; d ++){ 40 if(dis[cnt2][d] - dis[cnt1 - 1][d] > 0){ 41 break; 42 } 43 } 44 if(cc <= d){ 45 int cnt = abs(cnt2 - cnt1) + abs(y[i] - y[j]); 46 if(cnt <= k) ans ++; 47 }else{ 48 int cnt = y[i] + y[j] - 2*d + abs(cnt2 - cnt1); 49 if(cnt <= k) ans ++; 50 } 51 } 52 } 53 } 54 printf("%d ", ans); 55 return 0; 56 }