HDU 4311,4312 Meeting point(曼哈顿距离，切比雪夫距离)

分类：杂题

hdu

题意：面上n个点，某点到其他点的曼哈顿距离最小和，切比雪夫距离最小和。

思路：对于切比雪夫距离可以转化为哈密顿距离，方法是将每个点的坐标逆时针旋转45度然后放大sqrt（2）倍，换成坐标表示也就是（x,y）->(x-y,x+y).

对于第一个问题，求曼哈顿距离最小和，也就是sum（xj-xi）+sum(yj-yi)。

如果直接求时间复杂度无法承受。

所以我们可以先对x排序，对于从左到右的sum（x）我们可以递推出来，即sumx[tj[i].id] = sumx[tj[i-1].id] + (2*i-n)*(tj[i].x-tj[i-1].x);

对于y同理。

附4312代码

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long #define pii pair<int,int>using namespace std; const int maxn = 100000 + 500;//const int INF = 0x3f3f3f3f;LL disx[maxn], disy[maxn];LL sumv[maxn];struct Point {int x, y, id;Point(int x=0, int y=0, int z=0) : x(x), y(y), id(z) {} } tj[maxn];bool cmp1(Point A, Point B) {return A.x < B.x;}bool cmp2(Point A, Point B) {return A.y < B.y;}int main() {//freopen("input.txt", "r", stdin);int t; cin >> t;while(t–) {int n;cin >> n;for(int i = 0; i < n; i++) {int u, v;scanf("%d%d", &u, &v);tj[i] = Point(u-v, u+v, i);}sort(tj, tj+n, cmp1);disx[tj[0].id] = 0;for(int i = 1; i < n; i++) disx[tj[0].id] += (LL)tj[i].x – (LL)tj[0].x;for(int i = 1; i < n; i++) disx[tj[i].id] = disx[tj[i-1].id] + (LL)(2*i-n)*(LL)(tj[i].x-tj[i-1].x);sort(tj, tj+n, cmp2);disy[tj[0].id] = 0;for(int i = 1; i < n; i++) disy[tj[0].id] += (LL)tj[i].y – (LL)tj[0].y;for(int i = 1; i < n; i++) disy[tj[i].id] = disy[tj[i-1].id] + (LL)(2*i-n)*(LL)(tj[i].y-tj[i-1].y);LL ans = 100000000000000000;for(int i = 0; i < n; i++) {sumv[i] = disx[i] + disy[i];//cout << disx[i] << " " << disy[i] << endl;ans = min(ans, sumv[i]);}cout << ans/2 << endl;}return 0;}

上一篇HDU 5335 Walk Out（Bfs搜索字典序最小的最短路）

顶0踩0

宁愿停歇在你门前的那棵树上，看着你，守护你。

相关文章：

你感兴趣的文章：

标签云：