题解
圆圈表示特殊点 X表示必经点 S表示起点
左上角图表示找到经过X至少要经过最左最右必经点lr 使用数组排序二分查找
题目一共分四种情况(图片参考至某大佬) 代码将12和34合并为两种情况
最开始vec数组只保存题目所给特殊点 求出b线路最左最右必经点bl,br 之后加入起点s重新排序求出a最左最右必经点al,ar(情况1)
如果b站点没有点直接输出a区间长度(ar-al)*2+s点到ar或al距离(如果al ar包含s则为0)
如果b站点有必经点则al=min(al, bl) ar=max(ar, br) a区间不可能比b小
输出s到a距离+ab区间长+b区间小于a区间的部分(如图4上升后的←边)+2次跨越代价
数据好像水了补一个样例
10 3 1 2 4
6 0
7 0
9 1
8
输出16
AC代码
#include <stdio.h>#include <bits/stdc++.h>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int MAXR = 1e5 + 10;int x[MAXR], y[MAXR];int main(){#ifdef LOCALfreopen("C:/input.txt", "r", stdin) ;#endifint n, r, m, k, s, p;cin >> n >> r >> m >> k >> s; //n区间长 r经过点 m特殊点 k跨越代价 s起点位置for (int i = 1; i <= r; i++)scanf("%d%d", &x[i], &y[i]);vector<int> vec; //特殊点vec.push_back(1), vec.push_back(n);for (int i = 1; i <= m; i++)scanf("%d", &p), vec.push_back(p);sort(vec.begin(), vec.end());int al = n, ar = 1, bl = n, br = 1, f = 0; //ab最左右特殊点 f站点b有点for (int i = 1; i <= r; i++) //找到b站点每个必经点需要的最左最右特殊点if (y[i]){bl = min(bl, *(upper_bound(vec.begin(), vec.end(), x[i]) - 1)); //第一个小于等于x[i]的br = max(br, *(lower_bound(vec.begin(), vec.end(), x[i]))); //第一个大于等于f = 1;}vec.push_back(s), sort(vec.begin(), vec.end()); //s可以作为a的转向点for (int i = 1; i <= r; i++) //找a站点if (!y[i]){al = min(al, *(upper_bound(vec.begin(), vec.end(), x[i]) - 1));ar = max(ar, *(lower_bound(vec.begin(), vec.end(), x[i])));}al = min(al, bl), ar = max(ar, br); //a的范围至少要大于bif (!f)cout << (max(0, al - s) + max(0, s - ar) + ar - al) * 2 << endl; //s到a+a区间长*2elsecout << (max(0, al - s) + max(0, s - ar)) * 2 + //s到aar - al + br - bl + //ab区间长bl - al + ar - br + //a超出bk * 2 << endl; //跨越return 0;}
