0

我如何正确解决这个问题Benny 和 Segments。为这个问题给出的解决方案是不正确的。根据这个问题的社论，以下是正确的解决方案。

import java.io.*; import java.util.*;
class Pair{
    int a; int b;
    public Pair(int a , int b){ this.a = a; this.b = b;}
}

class TestClass {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static void rl() throws Exception{st = new StringTokenizer(br.readLine());}
    static int pInt() {return Integer.parseInt(st.nextToken());}
    public static void main(String args[] ) throws Exception {
        rl();
        int T = pInt();
        while(T-- > 0){
            rl();
            int N = pInt();
            int L = pInt();
            Pair[] p = new Pair[N];
            for(int i = 0; i < N; i++){
                rl();
                int l = pInt();
                int r = pInt();
                p[i] = new Pair(l, r);
            }
            Arrays.sort(p, new Comparator<Pair>(){
                @Override
                public int compare(Pair o1, Pair o2)
                {
                    return o1.a - o2.a;
                }
            });
            boolean possible = false;
            for(int i = 0; i < N; i++){
                int start = p[i].a;
                int curr_max = p[i].b;
                int req_max = p[i].a + L;
                for(int j = 0; j < N; j++){
                    if(p[i].a <= p[j].a &&  p[j].b <= req_max){
                        curr_max = Math.max(curr_max, p[j].b);
                    }
                }
                if(curr_max == req_max ){
                    System.out.println("Yes");
                    possible = true;
                    break;
                }
            }
            if(!possible)
            System.out.println("No");
            
        }

    }
}

但这对于以下测试用例肯定会失败。当它应该给出“否”时，它会给出“是”，因为没有长度为3的连续路径。

1
3 3
1 2
3 4
4 5

正如kcsquared所建议的那样。我修改了我的代码。

它运行正确。我认为问题制定者为这个问题设置了弱测试用例。

4

1 回答 1

1

正如您的测试用例所展示的，错误是在添加新段以扩展当前段时，没有测试来检查新段是否可以到达当前段或会留下间隙。为此，请将新段的左端与当前段的右端进行比较：

for(int j = i + 1; j < N; j++){
    if(p[j].a <= curr_max &&  p[j].b <= req_max){
        curr_max = Math.max(curr_max, p[j].b);
    }
}
于 2021-09-08T06:35:40.287 回答