USACO 2016 January Contest, Gold Problem 1. Angry Cows

原题下载

USACO2016-JAN-G1

答案

(Analysis by Brian Dean)

One approach for solving this problem is by combining a left-to-right scan with a right-to-left scan (one could call each scan either greedy or an example of dynamic programming). We first run a greedy/DP algorithm from left to right to determine for each hay bale the minimum power with which it must explode in order to propagate all the way left. We then do the same from right to left, computing for each hay bale the minimum power with which it must explode in order to propagate all the way to the right. Finally, by scanning through the list of hay bales, we can use these two numbers to identify the best "crossover" point where we should set the initial explosion.

Here is Mark Gordon's remarkably concise solution. Note how he uses a couple of clever tricks -- for example to run the algorithm from right to left, he simply reverses the input, runs the left-to-right algorithm, then reverses the output so it appears in the forward direction. Note also how he multiplies all haybale locations by 2 initially so only integer math is required; this eliminates any possibility of rounding error from using floating point numbers. This is why, for example, Mark uses "2 + max(..." in his final loop, since it would normally be "1 +" but the numbers are still scaled up by 2.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

#define INF 2000000000

int main() {
  freopen("angry.in", "r", stdin);
  freopen("angry.out", "w", stdout);

  int N; cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] *= 2;
  }
  sort(A.begin(), A.end());
  A.resize(unique(A.begin(), A.end()) - A.begin());

  vector<int> DP[2];
  for (int it = 0; it < 2; it++) {
    int lstj = 0;
    DP[it].resize(N, INF);
    DP[it][0] = -2;
    for (int i = 1; i < N; i++) {
      while (lstj + 1 < i && abs(A[i] - A[lstj + 1]) > DP[it][lstj + 1] + 2) {
        lstj++;
      }
      DP[it][i] = min(abs(A[i] - A[lstj]), DP[it][lstj + 1] + 2);
    }
    reverse(A.begin(), A.end());
  }
  reverse(DP[1].begin(), DP[1].end());

  int i = 0;
  int j = N - 1;
  int result = INF;
  while (i < j) {
    result = min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j])));
    if (DP[0][i + 1] < DP[1][j - 1]) {
      i++;
    } else {
      j--;
    }
  }
  cout << result / 2 << '.' << (result % 2 ? 5 : 0) << '\n';

  return 0;
}

Another (slightly slower, but still feasible) solution approach is illustrated by the following code by Nick Wu. It essentially does a binary search on the size of the first explosion. To test if a particular initial explosion size works, it then does a binary search for the location of the initial explosion.

import java.io.*;
import java.util.*;
public class angryGloglog {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("angry.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));

		int n = Integer.parseInt(br.readLine());
		TreeSet<Long> set = new TreeSet<Long>();
		for(int i = 0; i < n; i++) {
			set.add(2L*Integer.parseInt(br.readLine()));
		}

		long min = 0;
		long max = 1000000000;
		while(min != max) {
			long mid = (min+max)/2;
			long l = set.first();
			long r = set.last();
			while(l < r) {
				long m = (l+r+1)/2;
				if(possibleFirst(set, m, mid)) {
					l = m;
				}
				else {
					r = m-1;
				}
			}
			if(possibleLast(set, l, mid)) {
				max = mid;
			}
			else {
				min = mid+1;
			}
		}
		
		pw.printf("%.1f\n", min / 2.0);
		pw.close();
	}

	public static boolean possibleFirst(TreeSet<Long> set, long start, long r) {
		if(set.first() < start - r) {
			long curr = set.ceiling(start - r);
			long currRadius = r-2;
			while(curr != set.first()) {
				long next = set.ceiling(curr - currRadius);
				if(next >= curr) {
					return false;
				}
				curr = next;
				currRadius-=2;
			}
		}
		return true;
	}
	
	public static boolean possibleLast(TreeSet<Long> set, long start, long r) {
		if(set.last() > start + r) {
			long curr = set.floor(start + r);
			long currRadius = r-2;
			while(curr != set.last()) {
				long next = set.floor(curr + currRadius);
				if(next <= curr) {
					return false;
				}
				curr = next;
				currRadius-=2;
			}
		}
		return true;
	}

}