某天中午你很餓很餓很餓非常餓餓到不行!
可是你已經和人約好中午要去練習寫程式,
因此你決定用最快的速度吃飽後前往電教,
而不同的餐點可以帶來不同程度的飽足感,
假設你吃每份餐點的都只會花一單位時間,
且同樣的餐點你不願意午餐時間內吃兩次,
請問你至少要花多久的時間才能吃到飽呢?
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行有兩個正整數 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