1854 - 排队打饭
时间限制 : 3 秒
内存限制 : 128 MB
一天中午,有 N 个学生来到食堂买饭,他们需要排成了一个一字队伍并按顺序打饭,现在已经知道了每个人买饭的时间, 现在食堂的管理员希望知道他们按照怎样的顺序买饭能够使得所有人等待时间的总和最小。(每个人等待的时间 = 排在他前面的人的打饭时间和 + 自己打饭的时间)
题目输入
一个整数 T(T≤30)表示数据组数,每组数据包括两行,第一行一个整数 N 表示人数,第二行 N 个整数表示每个人买饭所需要的时间,所有整数均不超过 100。
题目输出
每组数据输出一行,包括一个整数,表示所有人等待时间总和的最小值。
输入/输出样例
输入格式
2 5 1 2 3 4 5 5 45 10 48 37 9
输出格式
35 334
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); } }
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; }
Java解答
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int T=sc.nextInt(); while(T-->0) { int N=sc.nextInt(); int arr[]=new int[N]; int sumTimes=0; for(int i=0;i<N;i++) { arr[i]=sc.nextInt(); } Arrays.sort(arr); for(int i=0;i<N;i++) { for(int j=0;j<=i;j++) { sumTimes+=arr[j]; } } System.out.println(sumTimes); } } }