C1666 [Wannafly冬令营2018Day4]夺宝奇兵(直接贪心)

题目链接：https://www.cometoj.com/problem/1666

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int n, m;
ll ans;

struct node{
	int x, y;
} point[maxn * 2];

int dis(node p1, node p2)		//计算两点之间要走的步数
{
	return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

ll GetAns(int a1, int a2, int b1, int b2)
{
	int d1 = dis(point[a1], point[b1]);
	int d2 = dis(point[a1], point[b2]);
	int d3 = dis(point[a2], point[b1]);
	int d4 = dis(point[a2], point[b2]);
	return min(d1 + d4, d2 + d3);
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= 2 * n; i++)
		cin >> point[i].x >> point[i].y;
  
	ans = dis(point[2 * n], point[2 * n - 1]);
	int a1 = 1, a2 = 2;
	for (int i = 2; i <= n; i++)
	{
		int b1 = i * 2 - 1, b2 = i * 2;
		ans += GetAns(a1, a2, b1, b2);
		a1 = b1, a2 = b2;
	}

	cout << ans << endl;

	return 0;
}