題目

思路

注意的點:

1.子數(shù)組的下標從1開始,開內(nèi)存時方便起見可以多開一個內(nèi)存;

2.L和U的元素和可能因為可能情況眾多而導(dǎo)致超過int范圍,應(yīng)用longlong存儲.

優(yōu)化:

代碼

無優(yōu)化:

#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];???//子數(shù)組
????????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++)????//子數(shù)組的元素個數(shù)有可能為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;
}


優(yōu)化:

#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];???//子數(shù)組
????????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++)????//子數(shù)組的元素個數(shù)有可能為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;
}