NYOJ 497-排队打饭

刺骨的言语ヽ痛彻心扉 2022-08-20 04:16 172阅读 0赞

## 排队打饭 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 2

描述

一天中午,有 N 个学生来到食堂买饭,他们需要排成了一个一字队伍并按顺序打饭,现在已经知道了每个人买饭的时间, 现在食堂的管理员希望知道他们按照怎样的顺序买饭能够使得所有人等待时间的总和最小。(每个人等待的时间 = 排在他前面的人的打饭时间和 + 自己打饭的时间)

输入

一个整数 T(T≤30)表示数据组数,每组数据包括两行,第一行一个整数 N 表示人数,第二行 N 个整数表示每个人买饭所需要的时间,所有整数均不超过 100。

输出

每组数据输出一行,包括一个整数,表示所有人等待时间总和的最小值。

样例输入

2
    5
    1 2 3 4 5
    5
    45 10 48 37 9

样例输出

35
    334

来源

[山东大学 ACM/ICPC 校赛高年级组试题 2012][ACM_ICPC _ 2012]

上传者

[ACM\_李如兵][ACM]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[100000];
    bool cmp(int x,int y)
    {
    	return x<y;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int n;
    		int i,j;
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&map[i]);
    		}
    		sort(map,map+n,cmp);
    		int xx=0;
    		int ans=0;
    		for(i=0;i<n;i++)
    		{
    			ans+=(xx+map[i]);
    			xx+=map[i];
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[ACM_ICPC _ 2012]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E5%B1%B1%E4%B8%9C%E5%A4%A7%E5%AD%A6+ACM%2FICPC+%E6%A0%A1%E8%B5%9B%E9%AB%98%E5%B9%B4%E7%BA%A7%E7%BB%84%E8%AF%95%E9%A2%98+2012
[ACM]: http://acm.nyist.net/JudgeOnline/profile.php?userid=ACM_%E6%9D%8E%E5%A6%82%E5%85%B5

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关排队打水(Java)

排队打水有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？输入格式第一

痛定思痛。/ 2024年03月30日 11:31/ 0 赞/ 67 阅读

相关排序不等式 AcWing 913. 排队打水

排序不等式 AcWing 913. 排队打水原题链接 [AcWing 913. 排队打水][AcWing 913.] 算法标签贪心排序不等式思路

蔚落/ 2023年09月28日 11:03/ 0 赞/ 114 阅读

相关 NYOJ 278 排队

排队时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述周末了，软件ACM的队员准备玩玩游戏，娱乐一下，CY想了一个好主意，所有队员站

偏执的太偏执、/ 2022年08月25日 02:02/ 0 赞/ 124 阅读

相关 NYOJ 497-排队打饭

排队打饭时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述一天中午,有 N 个学生来到食堂买饭,他们需要排成了一个一字队伍并按顺序打

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 04:16/ 0 赞/ 173 阅读

相关小鑫の日常系列故事（九）——排队买饭

小鑫の日常系列故事（九）——排队买饭 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述小鑫的

缺乏、安全感/ 2022年08月10日 09:55/ 0 赞/ 187 阅读

相关排队打饭

排队打饭 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述一天中午，有N个学生来到食堂买饭，

缺乏、安全感/ 2022年08月10日 08:41/ 0 赞/ 169 阅读

相关数据结构实验之队列一:排队买饭

数据结构实验之队列一:排队买饭 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述中午买饭的人

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 06:11/ 0 赞/ 159 阅读

相关数据结构实验之队列一:排队买饭

think:最近在做栈和队列的题目，但是一直如陷泥沼，今天终于在队列方面有了一点点突破口。希望借此机会反思一下自己最近的状态。最近的进度卡顿，很可能是因为自己在假期过于放松，半

妖狐艹你老母/ 2022年07月11日 13:02/ 0 赞/ 200 阅读

相关数据结构实验之队列一:排队买饭

Problem Description 中午买饭的人特多,食堂真是太拥挤了,买个饭费劲,理工大的小孩还是很聪明的,直接奔政通超市,哈哈,确实,政通超市里面也卖饭,有好几种

拼搏现实的明天。/ 2022年07月11日 04:26/ 0 赞/ 151 阅读

相关排队买饭

链式存储的队列问题：数据结构实验之队列一:排队买饭 Time Limit: 1000MS Memory Limit: 65536KB [S

Bertha 。/ 2022年06月10日 01:49/ 0 赞/ 265 阅读