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协议进行授权 , 转载请注明超时了,求大神指点更好的解题思路