Code Bye

超时了，求大神指点更好的解题思路

码拜
 

题目内容如下：

本人代码如下：（提交后OJ返回Time Limit Exceeded ，求大神指点更好的解题思路）

#include<stdio.h>

int a[1000001];

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

    scanf(“%d”,&T);

    while(T–)
    {
        scanf(“%d%d”,&n,&k);

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

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

        for(i=1;i<n;i++)
            for(t=i+1;t<=n;t++)
            if(a[i]>a[t])
        {
            temp=a[i];
            a[i]=a[t];
            a[t]=temp;
        }

        printf(“%d\n”,a[(n+1)/2]);
    }

    return 0;
}

运行正常。
我用的是Dev-C++，超时可能和你的编译工具有关。
把while的条件改成T–>0，应该就可以了。
20分
从一个数组中寻找第K大的数，是不需要排序的，这题考的就是快速寻找中位数。
寻找中位数，堆排序？
20分
偷个懒，试下快速排序： 
int T, N, K, A, B;
int i, j;
int straw[1000000];
int cmp(int *a, int *b)
{
	return *a < *b;
}
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &N, &K);
		memset(straw, 0, sizeof(int) * 1000000);
		while (K--)
		{
			scanf("%d%d", &A, &B);
			for (i = A; i <= B; i++) straw[i]++;
		}
		qsort(straw, N, sizeof(int), cmp);
		printf("%d\n", straw[N / 2]);
	}
	return 0;
}
这个题目用循环，排序肯定都会超时。K个指令，每条指令都是区间更新，这个很明显使用线段树会比较合适。但不知道怎么在线段树中找到中位数。
引用 4 楼 zhangxiangDavaid 的回复:

偷个懒，试下快速排序：

int T, N, K, A, B;
int i, j;
int straw[1000000];
int cmp(int *a, int *b)
{
	return *a < *b;
}
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &N, &K);
		memset(straw, 0, sizeof(int) * 1000000);
		while (K--)
		{
			scanf("%d%d", &A, &B);
			for (i = A; i <= B; i++) straw[i]++;
		}
		qsort(straw, N, sizeof(int), cmp);
		printf("%d\n", straw[N / 2]);
	}
	return 0;
}

用了快排结果还是超时，还有改进的方法吗？
#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;
}
1、偷懒，用C++ STL 自带的nthelement 效率是O(N)的
2、自己实现nthelement，方法类似于快速排序，快速排序每次都找一个正确位置的元素，因此每一次找到那个正确位置的元素后，判断中点在它的左区间还是右区间，递归解决即可
我错了，我以为只是求中位数，那这样N*K肯定超时。
那就应该要用线段数区间修改了
引用 8 楼 jensenjiang 的回复:

我错了，我以为只是求中位数，那这样N*K肯定超时。
那就应该要用线段数区间修改了

本人菜鸟，求指教什么是线段区间修改？谢谢
我又看了看题目…原来那个样例只要输出最后的中位数呀！那你就按照指令模拟，最后再按我第一个回复的找一次中位数就好了
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明超时了，求大神指点更好的解题思路！