codeforces 159 Div2 A

A. Sockets time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Vasya has got many devices that work on electricity. He's got n supply-line filters to plug the devices, the i-th supply-line filter has a_isockets.

Overall Vasya has got m devices and k electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of k electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity.

What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.

Input

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 50) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains n space-separated integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 50) — number a_i stands for the number of sockets on the i-th supply-line filter.

Output

Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.

Sample test(s) input 3 5 33 1 2 output 1 input 4 7 23 3 2 4 output 2 input 5 5 11 3 1 2 1 output -1 Note

In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices.

One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.

 

水题，每加一个拖线板要占掉一个插头，把拖线板的插头书都减一，再排序就可以了。

 

附代码：

1 #include<iostream> 2 #include<cstdlib> 3 using namespace std; 4 int cmp( const void *a, const void *b) 5 { 6 return *(int*) b-*(int*)a; 7 } 8 9 int arr[50]={0}; 10 11 int main(void) 12 { 13 int n, m, k, ans=0, sum=0; 14 int i; 15 16 cin>>n>>m>>k; 17 for( i=0; i<n; i++) 18 { 19 cin>>arr[i]; 20 } 21 qsort( arr, n, sizeof( int), cmp); 22 sum+=k; 23 i=0; 24 while( sum<m) 25 { 26 if( i==n) 27 { 28 ans=-1; 29 break; 30 } 31 sum+=arr[i]; 32 sum-=1; 33 i++; 34 ans++; 35 } 36 cout<<ans<<endl; 37 38 return 0; 39 }

 

转载于:https://www.cnblogs.com/shadow-justice/archive/2013/01/19/2867898.html

相关资源：垃圾分类数据集及代码