work4/work_4.2/task4.cpp - develop - novd7/algirithms_sem2

work4/work_4.2/task4.cpp
94 строки2 KB
Новиков Владимир
Рабочая тетрадь 4.2
30 май 2026, 14:10
30 май 2026, 14:100a353cb
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

class MinHeap {
 private:
  std::vector<int> data;

  void siftUp(int index) {
    while (index > 0) {
      int parent = (index - 1) / 2;
      if (data[index] >= data[parent]) break;
      std::swap(data[index], data[parent]);
      index = parent;
    }
  }

  void siftDown(int index) {
    int size = data.size();
    while (true) {
      int left = 2 * index + 1;
      int right = 2 * index + 2;
      int smallest = index;

      if (left < size && data[left] < data[smallest]) {
        smallest = left;
      }
      if (right < size && data[right] < data[smallest]) {
        smallest = right;
      }

      if (smallest == index) break;

      std::swap(data[index], data[smallest]);
      index = smallest;
    }
  }

 public:
  void push(int value) {
    data.push_back(value);
    siftUp(data.size() - 1);
  }

  int top() const {
    if (data.empty()) return -1;
    return data[0];
  }

  void pop() {
    if (data.empty()) return;
    data[0] = data.back();
    data.pop_back();
    if (!data.empty()) {
      siftDown(0);
    }
  }

  bool empty() const { return data.empty(); }

  int size() const { return data.size(); }
};

int minCouriers(std::vector<int>& distances, int maxDistance) {
  std::sort(distances.begin(), distances.end());

  MinHeap couriersLoad;

  for (int dist : distances) {
    if (!couriersLoad.empty() && couriersLoad.top() + dist <= maxDistance) {
      int newLoad = couriersLoad.top() + dist;
      couriersLoad.pop();
      couriersLoad.push(newLoad);
    } else {
      couriersLoad.push(dist);
    }
  }

  return couriersLoad.size();
}

int main() {
  std::vector<int> distances = {5, 10, 3, 8, 12, 6};
  int maxDistance = 20;

  std::cout << "Максимальный маршрут курьера: " << maxDistance << std::endl;

  int result = minCouriers(distances, maxDistance);

  std::cout << "Минимальное количество курьеров: " << result << std::endl;

  return 0;
}