Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Domolaz
2 / 2 / 1
Регистрация: 16.09.2012
Сообщений: 16
#1

Порядковая статистика - C++

16.09.2012, 19:54. Просмотров 1182. Ответов 7
Метки нет (Все метки)

http://acm.timus.ru/problem.aspx?space=1&num=1306
Подскажите, пожалуйста, ошибку в алгоритме, не могу найти.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int partition(vector<int> &a,int l,int r){
    swap(a[l+rand()%(r-l+1)],a[r]);
    int mid = a[r];
    int i=l-1;
    for(int j=l;j<r;j++)
        if(a[j]<mid)
            swap(a[++i],a[j]);
    swap(a[i+1],a[r]);
    return i+1;
}
 
int get_st(vector<int> &a,int l,int r,int k){
    if(r==l) return a[r];
    int mid = partition(a,l,r);
    int c_el = mid -l+1;
    if(k==c_el)
        return a[mid];
    if(c_el>k)
        return get_st(a,l,mid-1,k);
    else
        return get_st(a,mid+1,r,k-c_el);
}
 
 
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    double res;
    if((n&1)==1)
        res = get_st(a,0,n-1,(n+1)/2);
    else {
        res = (get_st(a,0,n-1,n/2)+get_st(a,0,n-1,n/2+1)+0.0)/2;
    }
    cout.precision(10);
    cout << fixed;
    cout<<res;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2012, 19:54     Порядковая статистика
Посмотрите здесь:

Математическая статистика - C++
Число отечественных автомобилей превышает число иномарок в 1,6 раз. Отечественная машина ломается в среднем в 2,6 раз чаще иномарки. В...

Статистика встречаемости символов в файле - C++
В файле содержится какое либо сообщение, предложение или много предложений. Необходимо подсчитать количество каждого встречаемого символа...

Статистика вхождения слов в массиве файлов (~50Gb) - C++
Есть задача: собрать статистику вхождения слов в массиве файлов (~50Gb) с использованием библиотеки X (синтаксический анализатор)....

Вычислить среднее арифметическое и среднеквадратичное отклонение (статистика) - C++
Как сделать на C++ ? Есть где пример ? Тема: Статистика. Задача: Вычислить среднее арифметическое \mu и среднеквадратичное...

K-порядковая статистика на отрезке - Алгоритмы
Добрый день всем! Пытаюсь разобраться в решении задачи о k-порядковой статистике на отрезке Я знаю только решение с персистентным...

K-ая порядковая статистика на отрезке за logN на запрос (NlogN препроцессинг) - Алгоритмы
Доброго времени суток! Возник такой вопрос - как узнавать k-ую порядковую статистику на отрезке за logN на запрос (NlogN препроцессинг). Я...

Счетчик или порядковая нумерация - MS Access
Здравствуйте! Встала передо мной такая задача: в Акцесс нужно создать приложение, с помощью которого вносились бы данные с условием...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.09.2012, 20:20     Порядковая статистика #2
Цитата Сообщение от Domolaz Посмотреть сообщение
Подскажите, пожалуйста, ошибку в алгоритме, не могу найти.
Внимательнее читайте условие задачи. Цитата из условия:
Программа должна выдать значение медианы с точностью до одного десятичного знака.
А у Вас выводится 10 знаков после запятой.
Domolaz
2 / 2 / 1
Регистрация: 16.09.2012
Сообщений: 16
16.09.2012, 20:56  [ТС]     Порядковая статистика #3
Вердикт не поменялся: TLE 3.
Проблема не в этом, а в чем-то другом, но непонятно в чем. Все мои тесты проходит.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.09.2012, 21:59     Порядковая статистика #4
Цитата Сообщение от Domolaz Посмотреть сообщение
Вердикт не поменялся: TLE 3.
Проблема не в этом, а в чем-то другом, но непонятно в чем. Все мои тесты проходит.
Вердикт TLE 3 говорит о том что 3-ий тест не проходит по времени. Алгоритм правильный у Вас, но медленный. Нужно что-то придумывать побыстрее.
Domolaz
2 / 2 / 1
Регистрация: 16.09.2012
Сообщений: 16
16.09.2012, 23:09  [ТС]     Порядковая статистика #5
O(n) же.
Есть смысл построить кучу,но это уже nlogn, но мне нужно решить именно этим способом.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.09.2012, 06:50     Порядковая статистика #6
Цитата Сообщение от Domolaz Посмотреть сообщение
Есть смысл построить кучу,но это уже nlogn, но мне нужно решить именно этим способом.
если нужно решить именно этим способом, то попробуйте использовать не vector, а простой массив.

Добавлено через 18 минут
Цитата Сообщение от Domolaz Посмотреть сообщение
O(n) же.
у Вас не O(n)
Domolaz
2 / 2 / 1
Регистрация: 16.09.2012
Сообщений: 16
18.09.2012, 00:59  [ТС]     Порядковая статистика #7
у Вас не O(n)
Грубо : n + n/2 + n/4 + n/8 .... + 1 < 2n => O(n). Но это если идеальное разбиение. При случайном аналогично, но доказательство другое.
Поменял вектор на массив - 7 MLE. Вывод - нужно другое решение. Например, куча.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2012, 06:12     Порядковая статистика
Еще ссылки по теме:

Порядковая нумерация в Access с определенного числа. (по типу счетчика) - MS Access
Есть ли какой ни будь способ стартануть БД с определенного числа. По типу (счетчик). Например мне нужно не с &quot;1&quot; начинать а с &quot;245&quot;. И...

Статистика. - PHP
Как вставить с свою страницу форму со статистикой - сколько пользователей всего, за неделю и за последнин 24 часа. На этом сайте тоже такая...

СТАТИСТИКА - Теория вероятностей
пОДСКАЖИТЕ ПОЖАЛУЙСТА КАКУЮ ФОРМУЛУ НАДО ИСПОЛЬЗОВАТЬ ЧТОБЫ РЕШИТЬ ЭТУ ЗАДАЧУ:4) С вероятностью 0,95 вычислите предельную ошибку выборочной...

Статистика - Теория вероятностей
может кто то разбирается в статистике,помогите пожалуйста...последняя задача и никак( В базисном году среднедушевой реальный...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.09.2012, 06:12     Порядковая статистика #8
Цитата Сообщение от Domolaz Посмотреть сообщение
Вывод - нужно другое решение. Например, куча.
Пробуйте кучу.

Не по теме:

я по-моему кучей решал

Yandex
Объявления
18.09.2012, 06:12     Порядковая статистика
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru