我用了快排，但提交后还是超时了，请问有更好的解决方法吗？

题目如下：



代码如下：
#include<stdio.h>
#include<stdlib.h>

int a[1000000];

int cmp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}

int main()
{
    int T,n,k,i,t,x,y,temp;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&k);

        for(i=0; i<n; i++)
            a[i]=0;

        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&x,&y);
            for(t=x-1; t<=y-1; t++)
                a[t]++;
        }

        qsort(a,n,sizeof(int),cmp);

        printf("%d\n",a[n/2]);

    }

    return 0;
}

超时的原因可能是因为排序，实际上不需要完全排序，只要排到一半的顺序就可以了，下面的代码供参考，不知是否超时：
#include<stdio.h>
int a[1000000];

void  sort(int *a,int n)
{
    int i,j,k,t,m,left,right;
    m=n/2;
    k=0;
    left=0;
    right=n-1;
    while(1)
    {
        k=left;
        for(j=left+1;j<=right;j++)
           if(a[j]<a[left])
           {
                k++;
                if(j>k)
                   {t=a[k]; a[k]=a[j];  a[j]=t;}
            }
        t=a[left]; a[left]=a[k];a[k]=t;
        if(k==m)
            return ;
        else if(k<m) left=k+1;
        else right=k-1;

   }

}
   
int main()
{
    int T,n,k,i,t,x,y,temp;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&k);

        for(i=0; i<n; i++)
            a[i]=0;

        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&x,&y);
            for(t=x-1; t<=y-1; t++)
                a[t]++;
        }
        
        sort(a,n);
        printf("%d \n",a[n/2]);

    }

    return 0;
}

楼上的排序函数写的不错，不过就效率而言它与快排是一个级别的。

你们的算法中真正浪费时间的部分不是最后的排序，而是之前操作的统计。即

        for(i=1; i<=k; i++)
         {
             scanf("%d%d",&x,&y);
             for(t=x-1; t<=y-1; t++)
                 a[t]++;
         }

这部分代码。这部分的时间复杂度是O(n * k)。

你们的问题分析还不够深入，模型的构建太直白。也没有掌握算法效率分析的量化手段，建议在这方面加强学习训练。

试试这段代码。

#include <stdio.h>
#include <stdlib.h>

int cmp(const void * a, const void * b)
{
    return *(short int *)a - *(short int *)b;
}

short int g[1000002];

int main()
{
    int t, n, k, a, b, i;

    for(scanf("%d", &t); t--; printf("%d\n", g[(n + 1) >> 1]))
    {
        for(scanf("%d%d", &n, &k), i = 1; i <= n; g[i++] = 0);
        for(i = k; i-- && scanf("%d%d", &a, &b); g[a]++, g[b + 1]--);
        for(a = 0, i = 1; i <= n; i++) a += g[i], g[i] = a;
        qsort(g + 1, n, sizeof(g[0]), cmp);
    }

    return 0;
}

恩，学习了快排

三楼的思路巧妙，值得学习