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

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

Восстановить пароль Регистрация
 
Domolaz
2 / 2 / 1
Регистрация: 16.09.2012
Сообщений: 16
16.09.2012, 19:54     Порядковая статистика #1
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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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     Порядковая статистика
Еще ссылки по теме:

K-ая порядковая статистика на отрезке за logN на запрос (NlogN препроцессинг)
K-порядковая статистика на отрезке
Порядковая нумерация в Access с определенного числа. (по типу счетчика) MS Access

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

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

Не по теме:

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

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

Текущее время: 23:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru