7 solutions

  • 1
    @ 2022-2-14 18:20:02
    //贪心算法,局部最优
    #include<stdio.h>
    int array[100001];
    void quicksort(int left,int right){
    	if(left > right)
    	  return;
    	int i,j,t;
    	i = left;//左边哨兵 
    	j = right;//右边哨兵 
    	int temp = array[left];//设置基位 
    	while(i!=j){//当左右不相等的时候进行遍历
    	    while(array[j] >= temp && i < j)
    		j--;
    	    while(array[i] <= temp && i < j)
    		i++; 
    		if(i<j){
    			t = array[i];
    			array[i] = array[j];
    			array[j] = t;
    		}
    	}
    	array[left] = array[i];
    	array[i] = temp;
    	quicksort(left,i-1);
    	quicksort(i+1,right);
    	return;
    }
    int main(){
    	int n;
    	long long sum = 0;
    	scanf("%d",&n);
    	for(int i=0; i<n; i++){
    		scanf("%d",&array[i]);
    	}    
    	quicksort(0,n-1);
        for(int i=0; i<n; i++){
        	sum += array[i]*(n-i-1);
    	}
    	printf("%lld\n",sum);
    } 
    

    Information

    ID
    76
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    256
    Accepted
    81
    Uploaded By