USACO 2016 February Contest, Bronze Problem 3. Load Balancing

Category: 計算機國際競賽 Date: 2017年11月9日上午10:30

原題下載

USACO2016-FEB-B3

答案

(Analysis by Nick Wu)

There are a lot of possible fence combinations to consider - if we simply consider every possible even x-coordinate and every possible event y-coordinate, there would be? $500000^{2}$ ?different combinations which is far too many.

Let us take an extreme example where there are two cows, one at? $(1, 1)$ ?and the other at? $(999999, 999999)$ . Note that every even x-coordinate between? $2$ ?and? $999998$ ?yields exactly the same division of cows into quadrants, no matter which y-coordinate we pick. By the same logic, every even y-coordinate between? $2$ ?and? $999998$ ?yields exactly the same division of cows into quadrants.

Therefore, we can make the following observation - if we set the vertical fence at? $x = a$ ?but no cow is placed with an x-coordinate of? $a - 1$ , we can move the vertical fence to? $x = a - 2$ ?and still preserve the same division of cows into quadrants. Similarly, if we set the horizontal fence at? $y = b$ ?but no cow is placed with a y-coordinate at? $y = b - 1$ , we can move the horizontal fence to? $y = b - 2$ .

This means that we only need to place vertical fences where? $x = a$ ?and there is a cow with x-coordinate? $a - 1$ , and we only need to place vertical fences where? $y = b$ ?and there is a cow with y-coordinate? $b - 1$ .

This gives us at most ten thousand pairs to try, which is small enough.

Here is my Java code:

import java.io.*;
import java.util.*;
public class balancing {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("balancing.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("balancing.out")));
		
		// read in N, we can safely ignore B so we don't actually read the value
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		// create arrays to store locations of cows
		// cow i is at point (xLoc[i], yLoc[i])
		int[] xLoc = new int[n];
		int[] yLoc = new int[n];
		for(int i = 0; i < n; i++) {
			// read in location of cow i
			st = new StringTokenizer(br.readLine());
			xLoc[i] = Integer.parseInt(st.nextToken());
			yLoc[i] = Integer.parseInt(st.nextToken());
		}
		// in the absolute worst case, N cows will be in one quadrant
		int ans = n;
		for(int xIndex = 0; xIndex < n; xIndex++) {
			for(int yIndex = 0; yIndex < n; yIndex++) {
				// identify the fence location
				// vertical fence at x=xDiv
				// horizontal fence at y=yDiv
				int xDiv = xLoc[xIndex]+1;
				int yDiv = yLoc[yIndex]+1;
				int upperLeft = 0;
				int upperRight = 0;
				int lowerLeft = 0;
				int lowerRight = 0;
				// identify which quadrant each cows lands in
				for(int i = 0; i < n; i++) {
					if(xLoc[i] < xDiv && yLoc[i] < yDiv) {
						lowerLeft++;
					}
					if(xLoc[i] < xDiv && yLoc[i] > yDiv) {
						upperLeft++;
					}
					if(xLoc[i] > xDiv && yLoc[i] < yDiv) {
						lowerRight++;
					}
					if(xLoc[i] > xDiv && yLoc[i] > yDiv) {
						upperRight++;
					}
				}
				// figure out which region has the most cows
				int worstRegion = 0;
				if(upperLeft > worstRegion) {
					worstRegion = upperLeft;
				}
				if(upperRight > worstRegion) {
					worstRegion = upperRight;
				}
				if(lowerLeft > worstRegion) {
					worstRegion = lowerLeft;
				}
				if(lowerRight > worstRegion) {
					worstRegion = lowerRight;
				}
				// determine if we have found a better pair of fences
				if(worstRegion < ans) {
					ans = worstRegion;
				}
			}
		}
		// print the answer
		pw.println(ans);
		// close output stream
		pw.close();
	}
}