Omówienie zadania D. Renting Bikes

Omówienie zadania D. Renting Bikes

Szczegółowe omówienie zadania D. Renting Bikes z platformy Codeforces

https://youtu.be/RvhRrdDvc30?t=1392

Link do zadania:
https://codeforces.com/problemset/problem/363/D

Zadanie pochodzi  z platformy Codeforces:
https://tiny.pl/t69lp
Zadanie pokazuje algorytm Binary Search po wyniku:

https://youtu.be/RvhRrdDvc30?t=2525

——-
Poniżej kod wzorcowy do zadania użyty w powyższym omówieniu który otrzymuje 100%:
#include <bits/stdc++.h>
using namespace std;

const int MAX_TABLE = 1e5+7;
int boys_money[MAX_TABLE];
int bikes_cost[MAX_TABLE];
int number_of_boys, number_of_bikes, budget;

bool CanWeAchieveBikes(int number_of_checked_bikes) {
 int act_budget, difference;
 int i;
 
 if ( number_of_checked_bikes > number_of_boys )
    return false;

 act_budget = budget;
 for (i=0; i<number_of_checked_bikes; ++i) { difference = boys_money[number_of_boys-i-1] - bikes_cost[number_of_checked_bikes-i-1]; if ( difference >= 0 )
 	   continue;
 	act_budget = act_budget + difference;
 	if ( act_budget < 0 )
 	   return false;
 }
 return true;
}

int BinarySearchRight_Result (int left_border, int right_border) {
 int middle;
 while (left_border < right_border) { middle = (left_border + right_border + 1) / 2; if ( CanWeAchieveBikes(middle) == true ) left_border = middle; else right_border = middle - 1; } return left_border ; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int bikes_boys_can_rent, total_cost_of_renting, own_money_required; int i; cin >> number_of_boys >> number_of_bikes >> budget;
 
 for (i=0; i<number_of_boys; ++i) cin >> boys_money[i];
 for (i=0; i<number_of_bikes; ++i) cin >> bikes_cost[i];
 
 sort (boys_money, boys_money+number_of_boys);
 sort (bikes_cost, bikes_cost+number_of_bikes);

 bikes_boys_can_rent = BinarySearchRight_Result (0, number_of_bikes);

 total_cost_of_renting = 0;
 for (i=0; i<bikes_boys_can_rent; ++i) {
    total_cost_of_renting += bikes_cost[i];
 }
 own_money_required = total_cost_of_renting - budget;
 own_money_required = max (own_money_required,0);
 cout << bikes_boys_can_rent << " " << own_money_required << "\n";

 return 0;
}