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();
	}
}

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

往期文章阅读推荐：

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！

2027 USAAIO美国AI奥赛启动报名！MIT/谷歌/Jane Street集体站台！