USACO 2014 December Contest, Bronze Problem 1. Marathon

Category: 计算机国际竞赛 Date: 2017年12月5日上午11:07

原题下载

USACO2014-DEC-B1

答案

(Analysis by Nick Wu)

Our first instinct when trying to figure out which point to skip is to try all of them. If we choose to skip each point and compute the new distance directly, then it takes about $N$ operations to compute the distance and there are about $N$ points to check, giving us an algorithm which runs in about $N$ operations. This will be too slow when $N$ gets to be 100,000.

Let's take a closer look at what happens when you skip a specific point. If we number the points from 1 to $N$ , and skip point $K$ , then the path we take goes from point 1 to point $K - 1$ , then from point $K - 1$ to point $K + 1$ , and then from point $K + 1$ to point $N$ . The distance of this path is exactly equal to the following:

(total distance without skipping any points) - (distance between points $K - 1$ and $K$ ) - (distance between points $K$ and $K + 1$ ) + (distance between points $K - 1$ and $K + 1$ ).

If we compute the total distance without skipping any points beforehand, then figuring out how long the path is when we want to skip a specific point no longer requires $N$ operations! It only requires a constant number of operations, and that will be fast enough.

Here is my Java code:

import java.io.*;
import java.util.*;
public class marathon {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("marathon.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("marathon.out")));
    int n = Integer.parseInt(br.readLine());
    int[] x = new int[n];
    int[] y = new int[n];
    for(int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      x[i] = Integer.parseInt(st.nextToken());
      y[i] = Integer.parseInt(st.nextToken());
    }
    int totalDistance = 0;
    for(int i = 1; i < n; i++) {
      totalDistance += Math.abs(x[i] - x[i-1]) + Math.abs(y[i] - y[i-1]);
    }
    int largestSkip = 0;
    for(int i = 1; i < n-1; i++) {
      int noSkipDistance = Math.abs(x[i+1] - x[i]) + Math.abs(x[i] - x[i-1]) + Math.abs(y[i+1] - y[i]) + Math.abs(y[i] - y[i-1]);
      int skipDistance = Math.abs(x[i+1] - x[i-1]) + Math.abs(y[i+1] - y[i-1]);
      largestSkip = Math.max(largestSkip, noSkipDistance - skipDistance);
    }
    pw.println(totalDistance - largestSkip);
    pw.close();
  }
}

以上就是关于【USACO 2014 December Contest, Bronze Problem 1. Marathon】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！