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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！