Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

16.09.2012, 19:54. Просмотров 1299. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2012, 19:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Порядковая статистика (C++):

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

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

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

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

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

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

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

Добавлено через 18 минут
Цитата Сообщение от Domolaz Посмотреть сообщение
O(n) же.
у Вас не O(n)
0
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. Вывод - нужно другое решение. Например, куча.
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.09.2012, 06:12 #8
Цитата Сообщение от Domolaz Посмотреть сообщение
Вывод - нужно другое решение. Например, куча.
Пробуйте кучу.

Не по теме:

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

1
18.09.2012, 06:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2012, 06:12
Привет! Вот еще темы с ответами:

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

Статистика биржевой деятельности и статистика спроса - Экономика
Очень поджимают сроки, сдать нужно ЗАВТРА! Сам сделал 12 задач, думал и с этими справлюсь, но, к сожалению, совсем не выходит. Крайне...

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

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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