USACO 2016 US Open Contest, Bronze Problem 1. Diamond Collector

原题下载：

USACO2016-OPEN-B1

答案：

(Analysis by Nick Wu)

Imagine that we have already selected the smallest diamond that will be shown. We can then count exactly how many diamonds are no smaller than that one, but can also appear in the display case along with that diamond.

There are up to a thousand possible sizes for the smallest diamond, and at most one thousand diamonds to inspect, giving us roughly one million operations, which will be fast enough.

Here is my Java code demonstrating this solution.

import java.io.*;
import java.util.*;
public class diamond {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("diamond.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("diamond.out")));
		// read in N and K
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		// read in sizes of all the diamonds
		int[] list = new int[n];
		for(int i = 0; i < n; i++) {
			list[i] = Integer.parseInt(br.readLine());
		}
		int ans = 0;
		for(int i = 0; i < n; i++) {
			// list[i] will be the size of the smallest diamond in the case
			int amt = 0;
			for(int j = 0; j < n; j++) {
				// loop over all diamonds, see if this diamond can be arranged with the selected one
				if(list[j] >= list[i] && list[j] <= list[i] + k) {
					amt++;
				}
			}
			// update our answer
			if(amt > ans) {
				ans = amt;
			}
		}
		// print the answer
		pw.println(ans);
		pw.close();
	}
}