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

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！