SHARE
TWEET

Untitled

a guest Feb 21st, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <utility>
  3. #include <algorithm>
  4. #include <vector>
  5. о
  6. //так понимаю структура пары чтобы засунуть её в вектор (было дано)
  7. typedef std::pair <int, int> Segment;
  8.  
  9. //функция для сортировки по второму элементу
  10. bool sortbysec(const std::pair <int, int> &a, const std::pair <int, int> &b){
  11.     return a.second < b.second;
  12. }
  13.  
  14.  
  15. std::vector <int> get_covering_set(std::vector <Segment> segments) {
  16.   std::vector <int> result;
  17.  
  18.   // fix this function
  19.   // первый элемент добавляется всегда потому что является надежным шагом
  20.   int a = segments[0].second;
  21.   result.push_back(a);
  22.  
  23.   // смотрим если левый конец правого отрезка не превышает значения последнего добавленного то переходим к следующему
  24.  
  25.   for (std::size_t i = 1; i < segments.size(); i++) {
  26.      if(segments[i].first > a){
  27.           a = segments[i].second;
  28.           result.push_back(a);
  29.       }
  30.   }
  31.   return result;
  32. }
  33.  
  34. int main(void) {
  35.   int segments_count;
  36.   std::cin >> segments_count;
  37.   std::vector <Segment> segments(segments_count);
  38.   for (int i = 0; i < segments_count; i++) {
  39.     std::cin >> segments[i].first >> segments[i].second;
  40.   }
  41.  
  42.   //сортировка по правому концу
  43.   std::sort(segments.begin(), segments.end(), sortbysec);
  44.  
  45.   //просто проверял как отсортировался вектор
  46.   /*for(int i = 0; i < segments_count; i++){
  47.       std::cout << segments[i].first << " " << segments[i].second << std::endl;
  48.   }*/
  49.  
  50.   // вывод решения
  51.   std::vector <int> points = get_covering_set(segments);
  52.   std::cout << points.size() << std::endl;
  53.   for (std::size_t i = 0; i < points.size(); i++) {
  54.     std::cout << points[i] << " ";
  55.   }
  56.   std::cout << std::endl;
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top