Здравствуйте, подскажите у меня совсем ущербный алгоритм. Мне его как-то оптимизировать или что-то другое писать. У меня на 9 тесте TL(time limit), надо в 0,25 уложиться, а у меня 0,296 работает.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, a, b;
int f( vector<pair<int, int>> sx, pair<int, int> a) {
int l = 0, r = N;
while (r - l > 0) {
int m = (l + r) / 2;
if (sx[m] < a)
l = m;
else if (sx[m] > a)
r = m;
else
return m;
}
return l;
}
int main()
{
int a;
cin >> N;
vector<pair<int, int>> sy(N, make_pair(-1, -1));
vector<pair<int, int>> sx(N, make_pair(-1, -1));
vector<int> g(N, 0);
for(int i = 0; i < N; i++){
cin >> a;
cin >> b;
sx[i].first = a;
sx[i].second = b;
sy[i].first = a;
sy[i].second = b;
}
sort(sx.begin(), sx.end());
for(int i = 0; i < N; i++){
a = 0;
int h = f(sx, sy[i]);
for(int j = 0; j < h; j++){
if(sx[h].second > sx[j].second || (sx[h].second == sx[j].second && sx[h].first > sx[j].first))
a++;
}
g[a] += 1;
}
for(auto i : g){
cout << i << endl;
}
}
УСЛОВИЕ
Астрономы часто изучают звездные карты, на которых звезды представлены точками на плоскости, и каждая звезда имеет декартовы координаты. Назовем уровнем звезды количество звезд, расположенных не выше и не справа от данной звезды. Астрономы хотят узнать распределение уровней звезд.
Problem illustration
Например, посмотрите на карту, показанную на рисунке выше. Уровень звезды 5 равен 3 (он образуется тремя звездами с номерами 1, 2 и 4). А уровни звезд с номерами 2 и 4 равны 1. На этой карте есть только одна звезда уровня 0, две звезды уровня 1, одна звезда уровня 2 и одна звезда уровня 3.
Вы должны написать программу, которая будет подсчитывать количество звезд каждого уровня на данной карте.
Исходные данные
В первой строке дано целое число N – количество звезд (1 ≤ N ≤ 15000). Следующие N строк содержат целые числа Xi и Yi – координаты звезд (). В одной точке плоскости может быть только одна звезда. Звезды перечислены в порядке возрастания координаты Y. Звезды с одинаковыми координатами Y перечислены в порядке возрастания координаты X.
0 ≤ Xi, Yi ≤ 32000
Результат
Выведите N целых чисел, по одному числу в строке. В первой строке выведите количество звезд уровня 0, во второй – количество звезд уровня 1 и так далее, в последней строке выведите количество звезд уровня N − 1.
C/C++
Здравствуйте, подскажите у меня совсем ущербный алгоритм. Мне его как-то оптимизировать или что-то другое писать
Загоняешь все пары в массив, сортируешь по наименьшей (от левого нижнего угла) координате из пары:
pair l < pair r если min(l.x,l.y-max_y) < min(r.x, r.y-max_y) где max_y максимальная y координата из всех точек.
принимаешь начальный level = 0;
После этого бежишь от начала массива и сравниваешь координаты на перегруженное равенство
pair l == pair r если min(l.x,l.y-max_y) == min(r.x, r.y-max_y)
Пока сравнение истино - плюсуешь звезды count_star++.
Как только ложь - значит переход на новый уровень. Сохраняешь пару (level, count_star);
принимаешь новый level = count star, и продолжаешь цикл.
Ну и по мелочи - передавать vector следует по ссылке. Иначе при каждом вызове функции будет создаваться новый вектор, в него все копироваться, отрабатывать и потом удаляться. Так что если сделаете vector <pair<int int>>& sx - будет быстрее.
pair l < pair r если min(l.x,l.y-max_y) < min(r.x, r.y-max_y) где max_y максимальная y координата из всех точек.
принимаешь начальный level = 0;
После этого бежишь от начала массива и сравниваешь координаты на перегруженное равенство
pair l == pair r если min(l.x,l.y-max_y) == min(r.x, r.y-max_y)
Пока сравнение истино - плюсуешь звезды count_star++.
Как только ложь - значит переход на новый уровень. Сохраняешь пару (level, count_star);
принимаешь новый level = count star, и продолжаешь цикл.
Ну и по мелочи - передавать vector следует по ссылке. Иначе при каждом вызове функции будет создаваться новый вектор, в него все копироваться, отрабатывать и потом удаляться. Так что если сделаете vector <pair<int int>>& sx - будет быстрее.
Али ***
К сожалению методы сортировки указаны не верно. Если одна из координат совпадает - значит равны. Соответственно и < не правильно. Если не совпадают обе координаты то l.x-l.y < r.x-r.y;
32к штук двойным перебором - это 1024М сравнений. Что овердохрена.
Если они уже отсортированы по у, тебе надо просто посмотреть, которые из находящихся в массиве ниже имеют координату, меньше чем х. Это должно быть в 2 раза быстрее. И сортировка твоя тоже лишняя, я не знаток С, но сдаеццо мне, что эти пары могут быть запросто отсортированы по адресу.
Если они уже отсортированы по у, тебе надо просто посмотреть, которые из находящихся в массиве ниже имеют координату, меньше чем х. Это должно быть в 2 раза быстрее. И сортировка твоя тоже лишняя, я не знаток С, но сдаеццо мне, что эти пары могут быть запросто отсортированы по адресу.
Ты написал алгоритм за O(n^2), вряд ли такое в 0.25 на таких ограничениях уложится.
Здесь, скорее всего, ожидается алгоритм за O(n log n), нужна структура данных, умеющая за логарифм добавлять единицу в ячейку и считать сумму на префиксе.
В мои годы на такое писали дерево отрезков или фенвика, сейчас мб другая мета, смотри по своему учебному плану.
Плюс ещё замечание, хотя фундаментально это с ускорением вряд ли поможет:
int f( vector<pair<int, int>> sx, pair<int, int> a)
Здесь происходит копирование всего вектора при передаче в аргументв
Используй константную ссылку, хотя бы для sx
А ещё в стандартной библиотеке есть lower_bound и binary_search. Лучше используй их, а то я что-то твоему бинпоиску не сильно доверяю (хотя опять же, скорее всего, бинпоиск как таковой тебе здесь не понадобится).
Здесь, скорее всего, ожидается алгоритм за O(n log n), нужна структура данных, умеющая за логарифм добавлять единицу в ячейку и считать сумму на префиксе.
В мои годы на такое писали дерево отрезков или фенвика, сейчас мб другая мета, смотри по своему учебному плану.
Плюс ещё замечание, хотя фундаментально это с ускорением вряд ли поможет:
int f( vector<pair<int, int>> sx, pair<int, int> a)
Здесь происходит копирование всего вектора при передаче в аргументв
Используй константную ссылку, хотя бы для sx
А ещё в стандартной библиотеке есть lower_bound и binary_search. Лучше используй их, а то я что-то твоему бинпоиску не сильно доверяю (хотя опять же, скорее всего, бинпоиск как таковой тебе здесь не понадобится).
Виктор Василенко
Спасибо большое, сейчас буду что ни будь думать.
Похожие вопросы
- Можете подсказать по задаче или дать алгоритм задачи, код опять же не нужен
- Программирование, теория алгоритмов подсказать алгоритм действий.
- Алгоритмы. Бинарная сортировка
- На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Как оптимизировать код, чтобы не было превышения по времени к задаче (C++, динамическое программирование)?
- Как оптимизировать код, чтобы не было превышения по времени к задаче (C++)?
- Оптимизировать данный код
- Алгоритмы STL, sort, первичный и вторичный ключи для сортировки.
- Помогите ускорить алгоритм
- Напишите алгоритм подсчета цифр. Помогите.