作为一名java选手,该oj貌似没有设置java审核时间 结果超时了(对java超级不友好)
不过思路都是一样的 都用贪心解决 因为一个取一个来 1> n n> 1 思路如下
import java.util.Scanner; class Point { int X, Y; } public class Main { public static int Dis(Point Key1, Point Key2) { return Math.abs(Key1.X - Key2.X) + Math.abs(Key1.Y - Key2.Y); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); Point Treasure[][] = new Point[100001][2]; long Ans = 0; for (int i = 1; i <= N; ++i) { Treasure[i][0] = new Point(); Treasure[i][1] = new Point(); Treasure[i][0].X = sc.nextInt(); Treasure[i][0].Y = sc.nextInt(); Treasure[i][1].X = sc.nextInt(); Treasure[i][1].Y = sc.nextInt(); } for (int i = 1; i < N; ++i) { Ans += Math.min(Dis(Treasure[i][0], Treasure[i + 1][0]) + Dis(Treasure[i][1], Treasure[i + 1][1]), Dis(Treasure[i][0], Treasure[i + 1][1]) + Dis(Treasure[i][1], Treasure[i + 1][0])); } Ans += Dis(Treasure[N][0], Treasure[N][1]); System.out.println(Ans); } }
include
using namespace std;
struct Point {
int X, Y;
};
int Dis(Point Key1, Point Key2) {
return abs(Key1.X - Key2.X) + abs(Key1.Y - Key2.Y);
}
int N, M;
Point Treasure[100010][2];
long long Ans;
int main(int argc, char *argv[]) {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
scanf("%d%d", &Treasure[i][0].X, &Treasure[i][0].Y);
scanf("%d%d", &Treasure[i][1].X, &Treasure[i][1].Y);
}
for (int i = 1; i < N; ++i) {
Ans += min(Dis(Treasure[i][0], Treasure[i + 1][0]) + Dis(Treasure[i][1], Treasure[i + 1][1]),
Dis(Treasure[i][0], Treasure[i + 1][1]) + Dis(Treasure[i][1], Treasure[i + 1][0]));
}
Ans += Dis(Treasure[N][0], Treasure[N][1]);
printf("%lld\n", Ans);
return 0;
}
```