@Proshka17

Как ускорить решение на c++?

Добрый день!
Есть задача:
5f47bad8b58ee284984406.png
Я написал решение, но получаю TL(Time Limit). Подскажите пожалуйста, как можно ускорить программу?
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <chrono>
#include <set>
#include <fstream>

using namespace std;


///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



vector<vector<double>> vec1;

static bool func(vector<double>& e1, vector<double>& e2) {
  return (e1[0] == e2[0]) ? e1[1] > e2[1]:e1[0] < e2[0];
}

class Solnew {
public:

  map<double, double> st1;
  vector<long long> more;


  double bad = 0;

  void Doit() {

    sort(vec1.begin(), vec1.end(), func);

    for (long long i = vec1.size() - 1; i >= 0; --i) {
      auto it = st1.upper_bound(vec1[i][1]);
      if (it == st1.end()) more.push_back(i);
      st1.emplace(vec1[i][1], vec1[i][0]);
    }

    
    for (long long k = more.size() - 1; k >= 0; --k) {
      long long i = more[k];

      auto it = st1.upper_bound(vec1[i][0]);
      int flag = 0;
      for (auto iter = it; iter != st1.end() & !flag; ++iter) {
        if (vec1[i][1] < iter->second) flag = 1;
      }

      if (!flag) {
        bad++;
      }

    }

  }

};


int main() {

  ifstream f("input.txt");
  Solnew s;
  double count;
  f >> count;

  for (double i = 0; i < count; ++i) {
    double left;
    double right;
    f >> left;
    f >> right;
    vector<double> tmp = {left,right};
    vec1.push_back(tmp);
  }
  s.Doit();
  cout << s.bad;




  return 0;
}
  • Вопрос задан
  • 210 просмотров
Решения вопроса 1
@Mercury13
Программист на «си с крестами» и не только
Вы тут что-то ухитрились написать, но всё равно n². Потому и TL.

Пусть для каждого поддона длина — большее из измерений, ширина — меньшее. Теперь условие «поддон А можно поставить на поддон Б» упрощается.

Очевидно, что поддоны, которые нельзя поставить друг на друга, будут возрастать по одному измерению и убывать по другому. (Иначе мы сортанём по длине, по ширине тоже обнаруживаем неубывание — и, сюрприз, эти поддоны становятся!)

Получаем список поддонов, которые не становятся ни на кого. Проще всего хранить его в виде set с сортировкой по длине, при этом ширина убывает.

Нам приходит новый поддон. Упорядочиваем координаты, затем ищем в списке equal_range по длине.

Для «БОЛЬШЕЙ» части списка [LOWER_bound, end): наш поддон можно поставить на все эти поддоны по длине, и только на первые из них — по ширине. Если l_b=end, или наш поддон не встаёт на *l_b — добавляем поддон в список. Но не сразу, а после проверки меньшей части.

Для «МЕНЬШЕЙ» части списка [begin, UPPER_bound): все эти поддоны можно поставить на наш поддон по ДЛИНЕ, и только некоторый хвост [some_pallet, upper_bound) — по ширине. Находим этот кусок и исключаем из дерева.

А теперь вопрос: как хакнуть наш set, чтобы можно было проводить поиск за log n и по длине, и по ширине?
А для этого пишем свой объект-сравниватель, который можно переключать между двумя вариантами: length1<length2, либо width1>width2;

P.S. Не очень понятно условие «один поддон становится на другой» — ни из описания, ни из примера. Мой алгоритм — length1 <= length2, width1 <= width2. Если, например, оба строго меньше (length1 < length2, width1 < width2) — то большая часть будет [u_b, end), меньшая — [begin, l_b), и из-за непересечения этих частей не обязательно добавлять в список отложенно.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Health Samurai Санкт-Петербург
от 70 000 до 150 000 ₽
Sportmaster Lab Москва
от 80 000 до 170 000 ₽
21 сент. 2020, в 13:08
5000 руб./за проект
21 сент. 2020, в 13:04
25000 руб./за проект
21 сент. 2020, в 12:51
3000 руб./за проект