Monument Tour

本文主要是介绍Monument Tour，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题意:从矩形的左边任一条路（东西走向）进入，然后参观所有的纪念碑与博物馆，只能向上或向下移动，参观完纪念碑与博物馆后返回到进入时的那条路上，求走出城市时的最短路程。

思路:遍历x坐标轴，求出每个x坐标中的最大与最小y值，存入数组a中，然后排序，求出中位数，这个中位数就是汽车进入城市时的y坐标，然后计算从0—X汽车参观每个博物馆走的路程。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define ll long long
using namespace std;
const int N = 1e5+10;
vector<int>g[N];
vector<int>mid;void solve() { int X,Y,n;int x[N],y[N];int line[N],maxn=0,pos;int maxx[N],minn[N];cin>>X>>Y;cin>>n;memset(maxx,-1,sizeof(maxx));for(int i=0; i<X; i++) minn[i] = N*10;for(int i=1; i<=n; i++) {cin>>x[i]>>y[i];maxx[x[i]] = max(maxx[x[i]],y[i]);minn[x[i]] = min(minn[x[i]],y[i]);}for(int i=0; i<X; i++) {if(maxx[i]!=-1&&minn[i]!=N*10) {mid.push_back(maxx[i]);mid.push_back(minn[i]);}}sort(mid.begin(),mid.end());int len = mid.size();pos = mid[(len-1)/2];ll ans=0;for(int i=0; i<X; i++) {if(maxx[i]!=-1&&minn[i]!=N*10) {ans+=maxx[i]-minn[i]+abs(maxx[i]-pos)+abs(minn[i]-pos);}}cout<<ans+X-1<<endl;
}int main() {ios::sync_with_stdio(false);solve();return 0;
}

这篇关于Monument Tour的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---