2017计蒜之道初赛第五场-UCloud 机房的网络搭建

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

输入格式

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

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

输出格式

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

样例说明

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

样例输入

10 4 2 7 2 3

样例输出

3

题目大意：中文题

解题思路：

将分线器从大到小排序，优先用输出根数多的分线器。对于 非零 分线器集合 x_1,x_2,\ldots x_mx​1​​,x​2​​,…x​m​​，能接入的服务器总数为 \sum_{i=1}^{m}(x_i-1)+1∑​i=1​m​​(x​i​​−1)+1。

注意处理分线器个数为 $0$、服务器个数为 $0$、分线器的输出根数为 $0$ 的情况。

#include<iostream> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<cstdio> #include<map> #include<set> #include<cmath> #include<cctype> #include<cstdlib> #include<list> #include<iomanip> using namespace std; typedef long long LL; const int MAXN=1e3+10; const int INF=0x3f3f3f3f; int a[110]; int main() { int n,m; while(cin>>n>>m) { for(int i=1;i<=m;i++) { cin>>a[i]; } if(m!=0) sort(a+1,a+1+m,greater<int>());//降序 // for(int i=1;i<=m;i++) // cout<<a[i]<<" "; // cout<<endl; int ans=1; int cnt=0; if(n==0) { cout<<"0"<<endl; }else if(n!=0&&m==0) { if(n==1) cout<<"0"<<endl; else cout<<"Impossible"<<endl; }else if(n<=a[1]) { if(n==1) cout<<"0"<<endl; else cout<<"1"<<endl; }else { if(n==1) { cout<<"0"<<endl; continue; } cnt=a[1]; for(int i=2;i<=m;i++) { if(a[i]==0) continue; cnt+=(a[i]-1); ans++; if(cnt>=n) break; } if(cnt>=n) cout<<ans<<endl; else cout<<"Impossible"<<endl; } } return 0; }