Counting Haybales – omówienie zadania

Counting Haybales – omówienie zadania

Szczegółowe omówienie zadania Counting Haybales.

Link do powyższego omówienia zadania Counting Haybales:
https://youtu.be/GUMHq8RmZj4?t=1309
——-
Link do treści zadania Counting Haybales:
Zadanie pochodzi z dywizji srebrnej Amerykańskiej Olimpiady Informatycznej USACO:
http://www.usaco.org/index.php?page=dec16results
——-
Zadanie Counting Haybales to klasyczne zadanie wymagające algorytmy Binary Search:

https://youtu.be/GUMHq8RmZj4?t=2222

Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
——-

#include <bits/stdc++.h>
using namespace std;

const int MAX_HAYBELLS = 1e6 + 7;
int hayabels_locations [MAX_HAYBELLS];

int BinarySearch (int start, int end, int value) {
 int medium;
 if (hayabels_locations[0] > value)
    return -1;

 while (start != end) {
    medium = (start + end + 1) / 2;
    if (hayabels_locations[medium] <= value)
        start = medium;
    else
        end = medium - 1;
 }
 return start;
}


int main() {
 freopen("haybales.in", "r", stdin);
 freopen("haybales.out", "w", stdout);
 
 int number_of_haybels, number_of_queries;
 int from_value, to_value;
 int first_haybel_index, last_haybel_index;
 int haybels_in_interval;
 int i;

 cin >> number_of_haybels >> number_of_queries;

 for (i=0; i<number_of_haybels; ++i)
    cin >> hayabels_locations[i];

 sort (hayabels_locations, hayabels_locations+number_of_haybels);

 for (i=0; i<number_of_queries; ++i) {
    cin >> from_value >> to_value;

	first_haybel_index = BinarySearch (0, number_of_haybels-1, from_value-1);
	last_haybel_index = BinarySearch (0, number_of_haybels-1, to_value);
    haybels_in_interval = last_haybel_index - first_haybel_index ;
    cout << haybels_in_interval << "\n";
 }

 return 0;
}
Kod C++ programu Counting Haybales, który jest omówiony w powyższym filmie i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz