UCloud 机房的网络搭建（解题报告）

Dear 丶 2022-06-15 12:52 190阅读 0赞

UCloud 刚刚建立一个新机房，近日正在进行网络搭建。机房内有 nnn 台服务器和 mmm 个分线器，整个机房只有一个网线出口。分线器的作用是将一根网线转换成多根网线。蒜头君也知道每个分线器输出的最大网线根数（不一定要将分线器输出的每根线都用上），问你至少需要使用多少个分线器才能使得每台服务器都有网线可用。

### 输入格式 ###

第一行输入 n,m(0≤n,m≤100)n,m(0 \\le n,m \\le 100)n,m(0≤n,m≤100)。

第二行输入包含 mmm 个整数的数组 A(0≤Ai≤10)A(0 \\le A\_i \\le 10)A(0≤Ai≤10) 表示每个分线器输出的最大网线根数。

### 输出格式 ###

输出最少需要的分线器数量。若不能使得所有服务器都有网线可用，输出一行`Impossible`。

### 样例说明 ###

一共需要 333 个分线器，最大输出根数分别为 7,3,27,3,27,3,2，连接方法如下图所示：

[![6b5fda43238a51e9d6827a908d5bac1a24d8506e.png][]][6b5fda43238a51e9d6827a908d5bac1a24d8506e.png]

#### 样例输入 ####

10 4
    2 7 2 3

#### 样例输出 ####

思路：第一个分线器没有额外的开销，其余每个分线器都有额外的开销（需要1个接口）来连入网络，特别注意题目中如果只有1个机器，则不需要分线器的特殊情况。

package jisuanzhidao.chusai5;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class One {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		int m=scan.nextInt();
    		int [] a=new int[m];
    		int sum=0;
    		for(int i=0;i<m;++i){
    			a[i]=scan.nextInt();
    			sum+=a[i];
    		}
    		if(n<=1){
    			System.out.println("0");
    		}
    		else{
                            Arrays.sort(a);
    			int ans=1;
    			n-=a[m-1];
    			for(int i=m-2;i>=0&&n>0;--i){
    				if(a[i]==0){
    					break;
    				}
    				++ans;
    				n-=(a[i]-1);
    			}
    			
    			if(n<=0){
    				System.out.println(ans);
    			}
    			else{
    				System.out.println("Impossible");
    			}
    		}
    			
    		
    	}
    
    }

[6b5fda43238a51e9d6827a908d5bac1a24d8506e.png]: /images/20220615/c401123e0a9c4029b5a124f00c1f1eed.png