测试9为什么超时啊,想不到别的方法(能不用搜索吗,不是很会)
查看原帖
测试9为什么超时啊,想不到别的方法(能不用搜索吗,不是很会)
859012
L2022211395楼主2022/12/25 13:19
#include<stdio.h>
int getStandard(long long int array[],int low,int high);
void QuickSort(long long int array[],int low,int high);//快速排序
int main()
{
	int n;
	scanf("%d",&n);
	long long int num[n];
	long long int i=0;
	long long int pos=0;
	long long int time=0;
	for(i=0;i<n;i++)
	{
		scanf("%lld",&num[i]);
	}
	QuickSort(num,0,n-1);
	for(i=0;i<n;i++)
	{
		if(num[i]>pos)
		{
			time=time+(num[i]-pos)*6+6;
		}
		else if(num[i]==pos)
		{
			time++;
		}
		pos=num[i];
	}
	time+=pos*4;
	printf("%lld",time);
	return 0;
}
int getStandard(long long int array[],int low,int high) {
    long long int key = array[low];  //临时保存基准元素 
    while(low<high) {  
        //high指针从后向前遍历 , 元素比基准元素大则指针向前移动 比基准元素小则和基准元素交换 
        while(low<high && array[high]>=key){
            high--;
        }
        if(low<high){
            array[low] = array[high];  //赋值给第一个元素,因为第一个元素作为基准元素已经临时保存了,所可以直接赋值 
        }
        //low指针从前向后遍历 , 元素比基准元素小则指针向后移动 否则比基准元素大则和基准元素交换 
        while(low<high && array[low]<=key){
            low++;
        }
        if(low<high){
            array[high] = array[low];  //复制给high指针所指得位置,因为在11行已经赋值给array[low]了 
        }
    }
    array[low] = key;
    return low; 
}
void QuickSort(long long int array[],int low,int high){
    if(low<high){  //递归出口 
        long long int standard = getStandard(array,low,high);
        QuickSort(array,low,standard-1);  //比基准元素小的部分继续调用快速排序 
        QuickSort(array,standard+1,high);   //比基准元素大的部分继续调用快速排序 
    }
}
2022/12/25 13:19
加载中...