Быстрая сортировка

[Legioner93]

long int потому что кол-во атлетов до 100000, int недостаточно. А как его правильно объявлять? Я прочитал про qsort, но не смог разобраться в синтаксисе, чтобы применить для сортировки структуры Поэтому написал сам (даже не сам, а половину списал с какого-то учебника).

[venco]

Legioner93 в сообщении #373362 писал(а):

long int потому что кол-во атлетов до 100000, int недостаточно.

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

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

[Zealint]

venco в сообщении #373365 писал(а):

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

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

[Legioner93]

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

[Legioner93]

Всё заработало. Здесь

 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;
}

[lim0n]

Так будет лучше

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;
}