USACO 2016 January Contest, Bronze Problem 2. Angry Cows

原题下载

USACO2016-JAN-B2

答案
(Analysis by Nick Wu)
In this problem, we have a set of hay bales placed along the number line and we wish to explode as many of them as possible. When a hay bale explodes, it causes all subsequent hay bales caught in its explosion to explode at a slightly larger radius, possibly causing a huge chain reaction.

Because the number of hay bales is small, we can simulate the chain reaction of hay bales for every possible hay bale.

When we simulate the process for a single hay bale exploding, we can separate the explosion into two separate explosions, one that goes to the left along the number line and one that goes to the right on the number line. For the explosion that goes to the left, if it causes any hay bales to its left to explode, we only have to consider the portion of that hay bale's explosion that goes to the left. This is because the radius increases by 1, but the hay bale that just exploded had to be to the left of the prior hay bale by at least 1.

Because of this, when a hay bale explodes, we can fix the direction of the explosion. For a given hay bale, we can find the hay bale furthest from it that would be caught in the explosion. After we have done that, we can then simulate that hay bale exploding with an increased radius.

Here is my Java code demonstrating this.

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

		// read in N
		int n = Integer.parseInt(br.readLine());
		// read in the locations into an array
		int[] locations = new int[n];
		for(int i = 0; i < n; i++) {
			locations[i] = Integer.parseInt(br.readLine());
		}
		
		// sort the locations for convenience
		Arrays.sort(locations);
		
		int answer = 1;
		
		// loop over every possible hay bale, simulating the explosion starting from that hay bale
		for(int start = 0; start < n; start++) {
			// figure out the farthest hay bale to the left that explodes
			int leftMostExplosion = getExplosionIndex(locations, start, true);
			
			// figure out the farthest hay bale to the right that explodes
			int rightMostExplosion = getExplosionIndex(locations, start, false);
			
			// count the number of hay bales that explode
			int numExploded = rightMostExplosion - leftMostExplosion + 1;
			
			// if the number that explodes, and update our answer if we explode more hay bales 
			if(numExploded > answer) {
				answer = numExploded;
			}
		}
		
		// print the answer
		pw.println(answer);
		
		// close I/O
		pw.close();
	}
	
	/*
	 * This function takes in an array of hay bales, the index of the first hay bale that explodes, and the direction
	 * that the explosion will go in, and return the index of the farthest hay bale that ends up exploding in that
	 * direction.
	 * 
	 * If goLeft is true, we simulate the explosion going only to the left.
	 * Otherwise, we simulate the explosion going only to the right.
	 */
	public static int getExplosionIndex(int[] location, int startIndex, boolean goLeft) {
		int lastExplosionIndex = startIndex;
		int currentRadius = 1;
		// if the last hay bale that explodes is not either the left most haybale or the right hay bale, continue simulating explosions.
		while(lastExplosionIndex > 0 && lastExplosionIndex < location.length-1) {
			
			// lastExplosionIndex stores the index of the hay bale that we are currently simulating an explosion for
			int direction = 0;
			
			// figure out which direction to inspect hay bales
			if(goLeft) {
				direction = -1;
			}
			else {
				direction = 1;
			}

			/*
			 * check if the next closest hay bale is within the range of the explosion
			 * the next hay bale to check is at index (nextIndex + direction)
			 * to avoid an index out of bounds exception on the array, we must first check that it is betwen 0 and location.length-1.
			 * After that, we check if the distance between the two points is less than or equal to the explosion radius.
			 */
			int nextIndex = lastExplosionIndex;
			while(nextIndex + direction >= 0 && nextIndex + direction < location.length && Math.abs(location[nextIndex + direction] - location[lastExplosionIndex]) <= currentRadius) {
				nextIndex += direction;
			}
			
			/*
			 * At the end of the while loop, "nextIndex" stores the farthest hay bale that exploded due to the current one exploding.
			 * If no other hay bale explodes because of the current explosion, we break out of the while loop
			 */
			
			if(nextIndex == lastExplosionIndex) {
				break;
			}
			
			/*
			 * Otherwise, we now have a new hay bale to simulate an explosion for.
			 */
			
			lastExplosionIndex = nextIndex;
			currentRadius++;
		}
		return lastExplosionIndex;
	}
	
}