搭积木

[编程题]搭积木

热度指数：18547 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 50M，其他语言100M
算法知识视频讲解

小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？

定义每一个长方形的长 L 和宽 W ，袋子里面长方形的个数为 n 。

假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。

数据范围：长方形个数满足 $1 \le n \le 10^6 \$ ， $1 \le w \le l \le 2^{31}-1 \$

输入描述:

第一行为积木的总个数 N

之后一共有N行，分别对应于每一个积木的宽W和长L

输出描述:

输出总共可以搭的层数

示例1

输入

输出

算法知识视频讲解

Java

lmz9509

为什么我这种先排序在查找的方法，在数据达到10000行的时候会过不去呢？请大神么帮我看看了，谢谢！！！

import java.util.*;
public class Main{
        public static void main(String[] args){
            Scanner input = new Scanner(System.in);
            int N = input.nextInt();
            int[][] a = new int[N][2];
            for (int i = 0;i<N;i++){
                for (int j =0 ;j<2;j++){
                    a[i][j] = input.nextInt();
                }
            }

            //排序：升序,按第一位的升序排列，为了后面只用比较第二列数据做准备
            Arrays.sort(a, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[0]==o2[0])return o1[1]-o2[1];
                    return o1[0]-o2[0];
                }
            });

            //寻找最高的积木层数
            int count = 1;//起始层数为1
            int max = a[0][1];//中间数
            for(int i = 1;i<N;i++){
                if(max<=a[i][1]){
                    max = a[i][1];
                    count++;
                }
            }
            System.out.println(count);
            input.close();
   }
}

发表于 2020-04-17 12:04:01 回复(0)

Java

我永远喜欢平泽唯

请问一下各位大佬，为什么这个代码到了10000的长度之后，就不对了，通过率卡在了71.43，提示没有数据输入输出。

希望有大佬能帮帮帮我，用java写老是遇到这样的问题🤗🤗

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner s = new Scanner(System.in);
        int m = s.nextInt();
        
        int[][] nums =new int[m][2];
        for (int i = 0; i < m; i++) {
            nums[i][0] = s.nextInt();
            nums[i][1] = s.nextInt();
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>=o2[0])return 1;
                return -1;
            }
        });
        //利用贪心算法
        int len = 1;
        int[] dp = new int[m+1];
        dp[1] = nums[0][1];
        for(int i = 1;i<m;i++){
            if(nums[i][1]>=dp[len])dp[++len]=nums[i][1];
            else{
                int start = 1;
                int end = len;
                int pos = 1;
                while(start<=end){
                    int middle= (start+end)/2;
                    if (dp[middle] < nums[i][1]) {
                        pos = middle;
                        start = middle + 1;
                    }
                    else end = middle - 1;
                }
                dp[pos+1] = nums[i][1];
            }
        }
        System.out.println(len);
    }
}

发表于 2020-03-24 11:20:00 回复(0)

Java

shepherb

先排序，然后利用二分查找求长所组成的数组的最长非递减子列的长度，O(NlgN)

import java.util.*;
public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         Block[] arr = new Block[N];
         for (int i = 0; i < N; i++) {
             arr[i] = new Block(sc.nextInt(), sc.nextInt());
         }

         Arrays.sort(arr, new Comparator() {
             public int compare(Block b1, Block b2) {
                 return b1.W != b2.W ? b1.W - b2.W : b1.L - b2.L;
             }
         });

         int[] spera = new int[N];
         spera[0] = arr[0].L;
         int right = 0;
         int l = 0;
         int r = 0;
         int mid = 0;
         for (int i = 1; i < N; i++) {
             l=0;
             r=right;
             while (l <= r) {
                 mid = l + (r - l) / 2;
                 if (arr[i].L >= spera[mid]) {
                     l = mid + 1;
                 } else {
                     r = mid - 1;
                 }
             }
             right = Math.max(right, l);
             spera[l] = arr[i].L;
         }
        System.out.println(right + 1);
    }
}

class Block {
     public int W;
     public int L;
     public Block(int W,int L){
         this.W=W;
         this.L=L;
    }
}

编辑于 2019-07-20 14:33:25 回复(0)