题目

思路

注意的点:

1.子数组的下标从1开始,开内存时方便起见可以多开一个内存;

2.L和U的元素和可能因为可能情况众多而导致超过int范围,应用longlong存储.

优化:

代码

无优化:

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

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

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        int number[n];
        for(int j=0;j<n;j++)         
        {
            scanf("%d",&number[j]);
        }
        int tab[n*(n+1)/2+1];   //子数组
        for(int j=0;j<n*(n+1)/2+1;j++)  //初始化
        {
            tab[j]=0;
        }
        int p=1;         //下标从1开始
        for(int j=0;j<n;j++)   //确定首元素  
        {
            for(int k=1;k<=n-j;k++)    //子数组的元素个数有可能为1,2...n-j
            {
                for(int m=0;m<k;m++)  //求和
                {
                    tab[p]+=number[j+m];
                }
                p++;
            }
        }              
        qsort(tab,n*(n+1)/2+1,sizeof(int),cmp);     
        printf("case #%d:\n",i);
        for(int j=0;j<m;j++)
        {
            int L,U;
            scanf("%d %d",&L,&U);
            long long count=0;   //求L和U之间元素和  可能会超过int范围
            for(int k=L;k<=U;k++)
            {
                count+=tab[k];    
            }
            printf("%lld\n",count);
        }
    } 
    return 0;
}


优化:

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

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

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        int number[n];
        for(int j=0;j<n;j++)         
        {
            scanf("%d",&number[j]);
        }
        int tab[n*(n+1)/2+1];   //子数组
        for(int j=0;j<n*(n+1)/2+1;j++)  //初始化
        {
            tab[j]=0;
        }
        int p=1;         //下标从1开始
        for(int j=0;j<n;j++)   //确定首元素  
        {
            for(int k=1;k<=n-j;k++)    //子数组的元素个数有可能为1,2...n-j
            {
                for(int m=0;m<k;m++)  //求和
                {
                    tab[p]+=number[j+m];
                }
                p++;
            }
        }              
        qsort(tab,n*(n+1)/2+1,sizeof(int),cmp);     
        long long count[n*(n+1)/2+1];
        count[1]=tab[1];
        for(int j=2;j<n*(n+1)/2+1;j++)
        {
            count[j]=count[j-1]+tab[j];
        }
        printf("case #%d:\n",i);
        for(int j=0;j<m;j++)
        {
            int L,U;
            scanf("%d %d",&L,&U);
            printf("%lld\n",count[U]-count[L-1]);  //注意是L-1
        }
    } 
    return 0;
}