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

蔚落 2023-09-28 11:03 80阅读 0赞

## 排序不等式 AcWing 913. 排队打水 ##

### 原题链接 ###

[AcWing 913. 排队打水][AcWing 913.]

### 算法标签 ###

贪心 排序不等式

### 思路 ###

1 将 n n n个人装满水桶所需的时间从小到大进行排序  
2 从前往后枚举每一个人， 计算该人前缀和后减去自身打水时间， 为该同学等待最短时间， 累加即为所有人等待最短时间。

### 证明 ###

若按照其他顺序打水， 无法保证每位同学等待时间最短。

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    const int N = 100005;
    int a[N], b[N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n=read();
    	int sum1=0;
    	rep(i, 0, n){
    	    a[i]=read();
    	    sum1+=a[i];
    	}
    	sort(a, a+n);
    	b[0]=a[0];
    	rep(i, 1, n){
    	    b[i]=b[i-1]+a[i];
    	}
    	int sum=0;
    	rep(i, 0, n){
    	    sum+=b[i];
    	}
    	printf("%lld", sum-sum1);
    	return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 913.]: https://www.acwing.com/problem/content/description/915/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png

发表评论取消回复

表情：

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

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

相关阅读

相关排队打水(Java)

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

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

相关绝对值不等式 AcWing 104. 货仓选址

绝对值不等式 AcWing 104. 货仓选址原题链接 [AcWing 104. 货仓选址][AcWing 104.] 算法标签排序快速选择算法贪心

一时失言乱红尘/ 2023年09月28日 11:06/ 0 赞/ 67 阅读

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

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

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

相关 AcWing | 堆排序

题目内容 > 输入一个长度为n的整数数列，从小到大输出前m小的数。输入格式 > > 第一行包含整数n和m。 > > 第二行包含n个整数，表示整数数列。输出格式 >

叁歲伎倆/ 2022年12月20日 01:56/ 0 赞/ 121 阅读

相关算法提高打水问题

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

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

相关 NYOJ 497-排队打饭

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

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

相关排队打饭

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

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

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

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

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

相关贪心算法5： P1223排队接水

题目描述有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入输出格式输入格式：输入

深藏阁楼爱情的钟/ 2022年05月09日 12:38/ 0 赞/ 258 阅读

相关 Java 打水问题

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

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