798
48
Link bài
Thuật toán:
Code:
Thuật toán:
- Gọi số lượng lỗ cắm trên ổ cắm thứ i là Ai.
- Ta xác định số lượng ổ cắm cần dùng ít nhất bằng cách dùng lần lượt các ổ cắm lớn nhất đến nhỏ nhất.
- Xác định thứ tự ổ cắm bằng cách sắp xếp các ổ theo thứ tự từ lớn đến bé
- Sau mỗi lần nối thêm ổ cắm thứ i, số lượng lỗ cắm sẽ tăng thêm một lượng là Ai-1 (Do cần một lỗ để cắm ổ thứ i vào.
Code:
Mã:
#include <bits/stdc++.h>
using namespace std;
int n, m, a[57], ans;
bool comp(const int a, const int b){
return a > b;
}
void read(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
}
void run(){
sort(a+1, a+1+n, comp);
ans = 0;
int tong = 1, dem;
while(tong < m && ans <= n){
ans++;
tong = tong-1+a[ans];
}
if (ans <= n){
cout << ans;
} else {
cout << -1;
}
}
int main(){
read();
run();
return(0);
}
Chỉnh sửa cuối:
