2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 03:22 
Аватара пользователя
long int потому что кол-во атлетов до 100000, int недостаточно. А как его правильно объявлять? Я прочитал про qsort, но не смог разобраться в синтаксисе, чтобы применить для сортировки структуры :| Поэтому написал сам (даже не сам, а половину списал с какого-то учебника).

 
 
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 04:17 
Legioner93 в сообщении #373362 писал(а):
long int потому что кол-во атлетов до 100000, int недостаточно.
Практически на всех современных компиляторах (gcc - точно) int - 32 бита. Часто long int того же размера, но может быть и 64 бита, и тогда Ваш код будет работать неправильно из-за неправильного формата scanf и printf. Если уж используете long, то добавьте флаг l (маленькая L) к формату d: scanf("%ld", &num).

И научитесь пользоваться qsort. Если нет на то веских причин, то лучше использовать готовые стандартные функции, чем писать свои - ошибок меньше. Скорее всего и работать быстрее будет, т.к. стандартный qsort - не примитивный вариант, как у Вас, а содержит разные оптимизации типа выбора среднего элемента.

 
 
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 10:08 
venco в сообщении #373365 писал(а):
Скорее всего и работать быстрее будет, т.к. стандартный qsort - не примитивный вариант, как у Вас, а содержит разные оптимизации типа выбора среднего элемента.

Как то на олимпиаде предлагалась задача, где нужна сортировка массива где-то на миллион элементов. Все, кто пользовался стандартным qsort из <stdlib.h> упали по Time Limit. Оказалось, что жюри выдумали тест, который заставляет его работать за квадрат. Говорят также, что сортировку из stl так завалить не получается. Это было давно, да и на практике такие массивы чисел вряд ли попадутся. Но знать надо.

 
 
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 11:33 
Аватара пользователя
Флаг добавил, результат тот же. Программа всё еще не проходит тест с результатом "Wrong Answer". Тогда как этот же тест при использовании сортировки пузырьком проходит. Попробую разобраться в стандартной qsort.

 
 
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 12:34 
Аватара пользователя
Всё заработало. Здесь
Код:
while(uk<n)
нужно было не $n$, а $n-1$. Ошибку было трудно заметить. Приведу окончательный вариант кода для интересующихся.
Код:
#include "stdio.h"
#include "stdlib.h"

struct atl{long int s;long int m;};
int compare (const void * a, const void * b)
{
  return ( *(long int*)a - *(long int*)b );
}
int main()
{
    long int n,i,k,num,uk;
   struct atl temp;
    long long int sum;
   struct atl a[100000];
   scanf("%ld",&n);
   for(i=0;i<n;i++) {scanf("%ld %ld",&a[i].m,&a[i].s);}
   qsort(a, n, sizeof(a[0]), compare);
   num=-1; uk=-1; sum=0;
   while(uk<n-1)
   {
      uk++;
      if(a[uk].s>=sum)
      {
         sum=sum+(long long int)a[uk].m; num++;
      }
   }
   num++;
    printf("%ld",num);
   return 0;
}

 
 
 
 Re: Быстрая сортировка
Сообщение11.11.2010, 13:34 
Так будет лучше
Код:
int compare (const struct atl *a, struct atl *b)
{
    return (a->s - b->s);
}
и
Код:
int main()
{
    ...
    long int sum;    /* никто не поднимет >2000000 */
    ...
    sum=num=0;
    for (i=0; i<n; i++)
    {
        if (a[i].s >= sum)
        {
            num++;
            sum += a[i].m;
            if (sum > 2000000) break;
        }
    }
    printf("%ld", num);
    return 0;
}

 
 
 [ Сообщений: 21 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group