算法：零件分组

我不是女神ヾ 2023-06-30 08:39 9阅读 0赞

1461: 零件分组

题目描述  
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?

输入  
第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。

输出  
仅一行，即最少分成的组数。

样例输入  
5  
8 4 3 8 2 3 9 7 3 5  
样例输出  
2  
使用java实现了一个 但是还有一点小错误 希望大佬帮我指出来，谢谢啦！！！

大概的思想就是 先按照长度进行排序，然后第一个默认是一组 然后将剩余的往第一组中加入， 如果重量大于前边的则加入 如果不满足则 加入一个新的组中，  
然后继续向新的组中加入剩余的，以此类推。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            if (n<=0)
                return;
            int a[] = new int[n*2];
            for(int i = 0;i< n*2 ;i++){
                a[i] = in.nextInt();
            }
            //开始排序
            int b[] = new int[n*2];
            int minlen = a[0];
            int minwei = a[1];
            for(int j = 0;j< n ;j++){
                for(int i = 0; i< n ;i++) {
                    if (a[i*2] < a[minlen] ){
                        minlen = i*2 ;
                        minwei = i*2+1;
                    }
                    else if(a[i*2] == a[minlen]){
                        if(a[i*2+1] < a[minwei]) {
                            minlen = i * 2;
                            minwei = i * 2 + 1;
                        }
                    }
                }
                b[j*2] = a[minlen];
                b[j*2+1] = a[minwei];
                a[minlen] = 10001;
            }
            a = b;
            //开始分组
            int zu = 1;
            int currwei=a[1];
            a[1] = 0;
            int m = 1;//被处理的元素个数
            while(m<n) {
                for (int i = 0; i < n; i++) {
                    if (a[i * 2 + 1] > currwei) {
                        currwei = a[i * 2 + 1];
                        a[i * 2 + 1] = 0;
                        m++;
                    }
                }
                if(m == n)  break;
                currwei = 10001;
                for (int i = 1; i < n; i++) {
                    if (a[i * 2 + 1] < currwei && a[i * 2 + 1] != 0) {
                        currwei = a[i * 2 + 1];
                        a[i * 2 + 1] = 0;
                        m++;
                        zu++;
                        break;
                    } else if(i ==n && a[i * 2 + 1] == 0)
                        break;
                }
            }
            System.out.println(zu);
        }
    }