区间覆盖问题java

妖狐艹你老母 2022-05-26 12:44 166阅读 0赞

区间覆盖问题  
Time Limit: 1000 ms Memory Limit: 65536 KiB  
Submit Statistic  
Problem Description  
用i来表示x坐标轴上坐标为\[i-1，i\]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。  
现在要求画m条线段覆盖住所有的区间，  
条件是：每条线段可以任意长，但是要求所画线段的长度之和最小，  
并且线段的数目不超过m(1≤m≤50）。

Input  
输入包括多组数据，每组数据的第一行表示区间个数n和所需线段数m，第二行表示n个点的坐标。  
Output  
每组输出占一行，输出m条线段的最小长度和。  
Sample Input  
5 3  
1 3 8 5 11  
Sample Output  
7  
Hint  
注意：题目数据已于2018.4.16更新  
Source

import java.util.*;
    
    class myclass {
        int arr[];
        int n;
        int b[];
        int m;
    
        myclass(int a[], int n, int m) {
            this.arr = a;
            this.n = n;
            b = new int[205];
            this.m = m;
        }
    
        void sort(int a[], int n) {
            int i, j;
            int t;
            for (i = 0; i < n - 1; i++) {
                for (j = 0; j < n - i - 1; j++) {
                    if (a[j] > a[j + 1]) {
                        t = a[j + 1];
                        a[j + 1] = a[j];
                        a[j] = t;
                    }
                }
            }
        }
    
        void main() {
            int s, e;
            sort(this.arr, this.n);
            s = arr[0];
            e = arr[this.n - 1];
            for (int i = 0; i < this.n - 1; i++) {
                b[i] = arr[i + 1] - arr[i] - 1;
                // System.out.println(b[i]);
            }
            sort(b, n - 1);
            int i;
            i = n - 2;
            int l = arr[n - 1] - arr[0] + 1;
            m--;
            while (m > 0) {
                l -= b[i--];
                m--;
            }
            System.out.println(l);
        }
    }
    
    class Main {
        public static void main(String[] args) {
    
            Scanner ss = new Scanner(System.in);
            int n, m;
            final int mm = 205;
            while (ss.hasNextInt()) {
                n = ss.nextInt();
                m = ss.nextInt();
                int i, j;
                int s, e;
                int a[] = new int[mm];
                int b[] = new int[mm];
                for (i = 0; i < n; i++)
                    a[i] = ss.nextInt();
                if (m == n) {
                    System.out.println(m);
                } else {
                    myclass per = new myclass(a, n, m);
                    per.main();
                }
            }
    
            ss.close();
        }
    }