重叠的装饰

[编程题]重叠的装饰

热度指数：4770 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

我们部门需要装饰墙，但是墙非常非常的长，有一千万米。我们会按顺序贴很多海报在上面，这些海报相互之间会重叠，请问下，最后还能看到哪些？（只看到一部分也算）

输入描述:

N表示N张海报
接下来每一行代表海报的左右边界（上下默认全满），Li，Ri，均为整数，大于0，小于一千万。海报按输入顺序张贴。

输出描述:

有多少张海报是可见的

示例1

输入

输出

算法知识视频讲解

Java

又笨又懒不想上课

import java.util.*;
public class Main {
    public static void main(String args[]) {
        int min = Integer.MAX_VALUE;
        int max = -1;
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] temp = new int[10000001];
        for(int i = 1; i <= N; i++) {
            int Li = in.nextInt();
            int Ri = in.nextInt();
            min = Math.min(Li,Ri);
            max = Math.max(Ri,Li);
            for(int j = min; j <= max; j++) {
                temp[j] = i;
            }
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < temp.length; i++) {
            if(temp[i] != 0) 
                set.add(temp[i]);
        }
        System.out.println(set.size());
    }
}

发表于 2021-05-26 20:26:40 回复(0)

Java

JLU小浪

//复杂度过大，不能全部通过，有人改进一下吗
import java.util.Arrays;
import java.util.Scanner;
//50
public class Main {
    static int max = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Info[] arr = new Info[n];
		for(int i=0;i<n;i++){
			Info info = new Info();
			info.a = sc.nextInt();
			info.b = sc.nextInt();
			arr[i] = info;
            if(Math.max(info.a,info.b)>max){
                max = Math.max(info.a,info.b);
            }
		}
		int res = 0;
		for(int i=0;i<arr.length-1;i++){ //最后一个必然不能被覆盖
			if(!isCover(arr, i)){
				res++;
			}
		}
		System.out.println(res+1);
	}
	static class Info{
		public int a,b;
	}
	static boolean isCover(Info[] arr,int a){
		int[] temp = new int[max+1];
		for(int i=a+1;i<arr.length;i++){
		     Arrays.fill(temp,Math.min(arr[i].a, arr[i].b),Math.max(arr[i].a, arr[i].b)+1,10);
		}
		boolean res = true;
		for(int i=arr[a].a;i<=arr[a].b;i++){
			if(temp[i] != 10){
				res = false;
				break;
			}
		}
		return res;
	}
}

编辑于 2019-09-15 00:02:26 回复(0)