Java 打水问题

喜欢ヅ旅行 2022-03-27 08:20 211阅读 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

代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args)  {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int []arr = new int[n];
            for (int i = 0;i< n;i++){
                arr[i]=sc.nextInt();
            }
            Arrays.sort(arr);
            int sum = 0;
            for(int i=1; i<=m; i++){
                int p = n/m;
                if(n%m>=i)p++;
                for(int j = i-1; j<n; j+=m, p--)
                    sum += arr[j]*(p-1);
            }
            System.out.println(sum);
            //sc.close();
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关可谓足篮打水一场空

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

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

相关排队打水(Java)

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

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

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

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

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

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

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

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

相关算法提高打水问题

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

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

相关水王问题java解法

核心思想就是删除相应的比例，剩着为王，所占比例可以推广！ public class KingOfWater { public static voi

偏执的太偏执、/ 2022年09月25日 04:22/ 0 赞/ 202 阅读

相关 java水杯

Problem Description 天气逐渐变热了，准备考研的高童鞋打算在夏天来临之前自己动手造一个水杯，以备口渴，你知道，高童鞋是个很挑剔而且古怪的的人，他

叁歲伎倆/ 2022年06月16日 20:49/ 0 赞/ 171 阅读

相关 leetcode桶装水问题

class Solution { public: int maxArea(vector<int>& height) {

妖狐艹你老母/ 2022年06月06日 04:13/ 0 赞/ 192 阅读

相关 Java 打水问题

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

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

相关水池进水与出水问题 -- 线程 java

水池进水与出水问题 – 线程 java package com.xzy; / 有一个水池，水池的容量是固定的500L,一边为进水口,一

阳光穿透心脏的1/2处/ 2022年03月20日 11:26/ 0 赞/ 283 阅读