1854 - 排队打饭
一天中午,有 N 个学生来到食堂买饭,他们需要排成了一个一字队伍并按顺序打饭,现在已经知道了每个人买饭的时间, 现在食堂的管理员希望知道他们按照怎样的顺序买饭能够使得所有人等待时间的总和最小。(每个人等待的时间 = 排在他前面的人的打饭时间和 + 自己打饭的时间)
Input
一个整数 T(T≤30)表示数据组数,每组数据包括两行,第一行一个整数 N 表示人数,第二行 N 个整数表示每个人买饭所需要的时间,所有整数均不超过 100。
Output
每组数据输出一行,包括一个整数,表示所有人等待时间总和的最小值。
Examples
Input
2 5 1 2 3 4 5 5 45 10 48 37 9
Output
35 334
Solution C
#include<stdio.h> int a[1000],b[1000]; int main() { int T,N; scanf("%d",&T); while(T--) { int i,j,tem,s=0; scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&a[i]); for(i=0;i<N-1;i++) for(j=i+1;j<N;j++) if(a[i]>a[j]) { tem=a[j]; a[j]=a[i]; a[i]=tem; } b[0]=a[0]; for(i=1;i<N;i++) b[i]=a[i]+b[i-1]; for(i=0;i<N;i++) s+=b[i]; printf("%d\n",s); } }
Solution C++
#include<bits/stdc++.h> using namespace std; int a[1000000],ana=2,sum=0,n,d=1,min=100000,b[100000]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>d; sum=0;ana=2; for(int j=1;j<=d;j++) { cin>>a[j]; } sort(a+1,a+d+1); b[1]=a[1]; for(int k=2;k<=d;k++) { b[ana]=b[ana-1]+a[k]; //cout<<b[ana]; ana++; } for(int l=1;l<=d;l++) sum+=b[l]; cout<<sum<<endl; } return 0; }