Giải bài ntucoder CDIE - Cắm điện

Link bài

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;
    }
}

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);
}