java - USACO Diamond Collector 问题未通过测试用例

Question

这是问题描述：

这是我的代码：

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class DiamondCollector {

    public static void main(String[] args) throws IOException {
        List<String> input = new ArrayList<>();

        BufferedReader bufferedReader = new BufferedReader(new FileReader("diamond.in"));

        String line;
        while((line = bufferedReader.readLine()) != null) {
            input.add(line);
        }
        bufferedReader.close();

        String[] nk = input.get(0).split(" ");
        int numDiamonds = Integer.parseInt(nk[0]);
        int maxSizeDiff = Integer.parseInt(nk[1]);

        List<Integer> diamonds = new ArrayList<>();
        for(int i = 1; i < numDiamonds + 1; i++) {
            diamonds.add(Integer.parseInt(input.get(i)));
        }

        Collections.sort(diamonds);

        PrintWriter printWriter = new PrintWriter(new BufferedWriter(new FileWriter("diamond.out")));
        printWriter.println(getMaxDiamonds(diamonds, 0, maxSizeDiff, 0));
        printWriter.close();
    }

    public static Integer getMaxDiamonds(List<Integer> diamonds, int index, int maxSizeDiff, int total) {
        if(diamonds.isEmpty()) {
            return 0;
        }
        else if(index == 0) {
            return getMaxDiamonds(diamonds, index + 1, maxSizeDiff, 1);
        }
        else if(index == diamonds.size()) {
            return total;
        }
        else if(diamonds.get(index).equals(diamonds.get(index - 1))) {
            return getMaxDiamonds(diamonds, index + 1, maxSizeDiff, total);
        }

        if(diamonds.get(index) - diamonds.get(index - 1) > maxSizeDiff) {
            return Collections.max(Arrays.asList(total, getMaxDiamonds(diamonds, index + 1, maxSizeDiff, 1)));
        }
        else {
            return getMaxDiamonds(diamonds, index + 1, maxSizeDiff, total + 1);
        }
    }
}

*请注意，提交到usaco portal，不能有任何评论/javadocs/包信息供评分者接受提交

我采用了一种递归方法，试图以决策树的方式分解这个“最大菱形”问题。

即最大差异为 2, [1, 1, 2, 5, 6, 7]

getMaxDiamonds索引=0，总计=1

getMaxDiamonds索引=1，总计=1

getMaxDiamonds索引=2，总计=2

getMaxDiamonds索引=3, 总计=max(2, getMaxDiamonds([5, 6, 7]))=max(2, 3)=3

这就是我尝试实施我的解决方案的方式。

不幸的是，这个解决方案只通过了 1/10 的测试用例，所以我不确定我在这里忽略了什么？AFAIK USACO 不会告诉您有关失败的测试用例的任何信息，只是告诉您它们失败了。以前有没有人解决过这个问题和/或可以看到我的解决方案哪里出错了？

标签： javaalgorithm

Answer 1

我的评论是对的——这些单词问题的措辞很棘手，所以我下次肯定要花更多时间阅读问题。

这是我通过的解决方案。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class DiamondCollector {

    public static void main(String[] args) throws IOException {
        List<String> input = new ArrayList<>();

        BufferedReader bufferedReader = new BufferedReader(new FileReader("diamond.in"));

        String line;
        while((line = bufferedReader.readLine()) != null) {
            input.add(line);
        }
        bufferedReader.close();

        String[] nk = input.get(0).split(" ");
        int numDiamonds = Integer.parseInt(nk[0]);
        int maxSizeDiff = Integer.parseInt(nk[1]);

        List<Integer> diamonds = new ArrayList<>();
        for(int i = 1; i < numDiamonds + 1; i++) {
            diamonds.add(Integer.parseInt(input.get(i)));
        }

        Collections.sort(diamonds);

        PrintWriter printWriter = new PrintWriter(new BufferedWriter(new FileWriter("diamond.out")));
        printWriter.println(getMaxDiamonds(diamonds, maxSizeDiff));
        printWriter.close();
    }

    public static Integer getMaxDiamonds(List<Integer> diamonds, int maxSizeDiff) {
        int maxDiamonds = 0;
        for(int startIndex = 0; startIndex < diamonds.size(); startIndex++) {
            int currentIndex = startIndex + 1;
            int currentMax = 1;

            while(currentIndex < diamonds.size() && diamonds.get(currentIndex) - diamonds.get(startIndex) <= maxSizeDiff) {
                currentMax += 1;
                currentIndex += 1;
            }
            maxDiamonds = Collections.max(Arrays.asList(maxDiamonds, currentMax));
        }
        return maxDiamonds;
    }
}