ZeroJudge D804: 好餓

某天中午你很餓很餓很餓非常餓餓到不行!
可是你已經和人約好中午要去練習寫程式,
因此你決定用最快的速度吃飽後前往電教,
而不同的餐點可以帶來不同程度的飽足感,
假設你吃每份餐點的都只會花一單位時間
同樣的餐點你不願意午餐時間內吃兩次
請問你至少要花多久的時間才能吃到飽呢?

範例測資

範例輸入範例輸出
第一行有兩個正整數 N 和 M (N <= 100000)
代表有 N 種不同的餐點和需要 M 單位的飽足感才會吃飽。
第二行有 N 個不超過1000的正整數,分別代表第 1 種到第 N 種餐點的飽足感。
一個數字,代表至少吃幾份才會飽
如果不管怎樣都吃不飽請輸出「OAQ”」(不含雙引號)
5 10
8 5 3 2 1
2

解題思路

將食物收到一個一維陣列中,並且將其排序。從最右邊吃到最左邊並輸出吃的次數。

範例程式碼-ZeroJudge D804: 好餓

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int>num;
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    int sum = 0, count = 0;
    bool ok = false;
    for (int i = N-1; i>=0; i--) {
        sum += num[i];
        count++;
        if (sum >= M) {
            cout << count << "\n";
            ok = true;
            break;
        }
    }
    if (!ok) cout << "OAQ\n";
}

//ZeroJudge D804
//Dr. SeanXD

發佈留言