One day at noon, you were extremely, extremely, extremely hungry! But you had already made plans to practice programming with someone at noon. So you decided to eat quickly and then head to the computer lab as fast as possible. Different meals can bring different levels of satisfaction. Suppose you only take one unit of time to eat each meal, and you are unwilling to eat the same meal twice during lunchtime. How long would it take you at least to feel full?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two positive integers, N and M (N ≤ 100000). This represents N different types of meals and the need for M units of satisfaction to feel full. The second line contains N positive integers, each not exceeding 1000, representing the satisfaction level of each of the N types of meals. | A number representing the minimum number of servings needed to feel full. If it's impossible to feel full no matter what, output 'OAQ' (without quotation marks). |
| 5 10 8 5 3 2 1 | 2 |
Thought Process
Place the food into a one-dimensional array and sort it. Eat from the rightmost element to the leftmost and output the number of times eaten.
Sample Code－ZeroJudge D804: Lunch
#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