算法提高打水问题

阳光穿透心脏的1/2处 2022-09-27 06:21 116阅读 0赞

问题描述

N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。

输入格式

第一行两个正整数N M 接下来一行N个正整数Ti。  
　　N,M<=1000，Ti<=1000

输出格式

最小的等待时间之和。（不需要输出具体的安排方案）

样例输入

7 3  
3 6 1 4 2 5 7

样例输出

11

提示

一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。  
　　例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。  
　　第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6  
　　第二个龙头打水的人总等待时间 = 0 + 2 = 2  
　　第三个龙头打水的人总等待时间 = 0 + 3 = 3

所以总的等待时间 = 6 + 2 + 3 = 11

代码：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<string.h>
    using namespace std;
    int a[10001],b[1001][1001];
    int main()
    {
    	int i,j,k=0,x=0,n,m,sum=0;
    	scanf("%d%d",&n,&m);
    	for (i=0; i<n; i++)
    	{
    		cin>>a[i];
    	}
    	sort(a,a+n);
    	for (i=0; i<n; i++)
    	{
    		b[k++][x] = a[i];
    		if (k == m)
    		{
    			k=0;
    			x++;
    		}
    	}
    	for (i=0; b[i][0]; i++)
    	{
    		k=0;
    		while (b[i][k])
    		{
    			k++;
    		}
    		for (j=0; j<k-1; j++)
    		{
    			for (x=0; x<=j; x++)
    			{
    				sum+=b[i][x];
    			}
    		}
    	}
    	cout<<sum;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关可谓足篮打水一场空

天对中国足球和篮球来说，可以说是个特殊的日子，不是因为取得了怎样的成绩，而是因为我们得到了怎样的失败。篮联世界杯，正在中国如火如荼的举行，中国队虽然无缘16强的比赛，...

╰半橙微兮°/ 2024年04月18日 17:10/ 0 赞/ 28 阅读

相关排队打水(Java)

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

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

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

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

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

相关算法设计与分析——贪心算法——单个出水口打水问题

1.打水问题：有n个人去水房排队打水，只有一个出水口，且出水口流速恒定。每个人因为盛水的工具不一，打水所需的时间也不一致，设第i个人所需要的打水时间为ti；问如何安排打水顺序使

电玩女神/ 2022年10月15日 12:56/ 0 赞/ 130 阅读

相关算法提高打水问题

问题描述　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。输入格式　　第一行两个正整数N M 接下来一

阳光穿透心脏的1/2处/ 2022年09月27日 06:21/ 0 赞/ 117 阅读

相关算法提高扫雷

问题描述　　扫雷游戏你一定玩过吧！现在给你若干个n×m的地雷阵，请你计算出每个矩阵中每个单元格相邻单元格内地雷的个数，每个单元格最多有8个相邻的单元格。 0<n,m<=10

╰半橙微兮°/ 2022年09月27日 06:17/ 0 赞/ 134 阅读

相关算法提高计算器

【问题描述】　　王小二的计算器上面的LED显示屏坏掉了，于是他找到了在计算器维修与应用系学习的你来为他修计算器。　　屏幕上可以显示0~9的数字，其中每个数字由7个小

- 日理万妓/ 2022年09月26日 15:56/ 0 赞/ 121 阅读

相关算法二十二：倒水问题

问题描述邓老师有有 2 个容量分别为 n 单位、m 单位的没有刻度的杯子。初始，它们都是空的。邓老师给了你 t 分钟时间。每一分钟，他都可以做下面 4 件事中的任意

深碍√TFBOYSˉ_/ 2022年05月21日 08:07/ 0 赞/ 160 阅读

相关贪心算法6 排队接水问题

题目描述有n个人排队到r个水龙头去打水，他们装满水桶的时间t1, t2 , ……, tn为整数且各不相同，应如何安排他们的打水顺序才能使他们花费的总时间最少? 只有一组输

小咪咪/ 2022年05月09日 12:56/ 0 赞/ 191 阅读

相关 Java 打水问题

问题描述　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。输入格式　　第一行两个正整数N M 接下来一

喜欢ヅ旅行/ 2022年03月27日 08:20/ 0 赞/ 162 阅读