Вывести максимальное количество задач, которое Вася сможет решить.

@Sprashivalka · Регистрация: 10.12.2018

Студворк — интернет-сервис помощи студентам

В этой задаче Вася готовится к олимпиаде. Учитель дал ему N задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.

Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа N, A (1≤N≤100000, 0≤A≤109) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1≤ai≤109, 1≤bi≤109) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Формат выходных данных
Выведите одно число — максимальное количество задач, которое Вася сможет решить.
Примеры
входные данные выходные данные
3 2
3 1
2 1
1 1
выходные данные
3
входные данные
4 1
1 10
21 5
1 10
100 100
выходные данные
3

@L0M · 11.12.2018, 00:41

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Task {
    int skill, bonus;
};
 
typedef vector<Task> TaskVector;
 
int main() {
    int N, A;
    TaskVector tv;
    Task task;
 
    cin >> N >> A;
    for (int i = 0; i < N; ++i) {
        cin >> task.skill >> task.bonus;
        tv.push_back(task);
    }
 
    sort(tv.begin(), tv.end(), [](const Task &a, const Task &b) { return a.skill < b.skill; });
 
    int counter = 0;
    for (const auto &t : tv) {
        if (t.skill <= A) {
            ++counter;
            A += t.bonus;
        }
        else
            break;
    }
    cout << counter << endl;
 
    return 0;
}

@Sprashivalka 0 / 0 / 0 Регистрация: 10.12.2018 Сообщений: 3
		1
	Вывести максимальное количество задач, которое Вася сможет решить. 10.12.2018, 21:27. Показов 5535. Ответов 1 Метки нет (Все метки) В этой задаче Вася готовится к олимпиаде. Учитель дал ему N задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi. Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения? Формат входных данных Сначала вводятся два целых числа N, A (1≤N≤100000, 0≤A≤109) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1≤ai≤109, 1≤bi≤109) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения. Формат выходных данных Выведите одно число — максимальное количество задач, которое Вася сможет решить. Примеры входные данные выходные данные 3 2 3 1 2 1 1 1 выходные данные 3 входные данные 4 1 1 10 21 5 1 10 100 100 выходные данные 3 0

	11.12.2018, 00:41

Опции темы