排队打水算法实现

简介: 排队打水算法实现

算法分析

安排他们的打水顺序才能使所有人的等待时间之和最小,则需要将打水时间最短的人先打水

证明:

不妨设

(1)i1i1 ≠ i2i2 ≠ i3i3 ≠ … ≠ inin

(2)i1i1~inin属于[1,n][1,n]

(3)t1t1 < t2t2 < t3t3 <… < tntn,

1、由i的任意性,打水的时间总和为ti1ti1 * (n - 1) + ti2ti2 * (n - 2) + … + tintin * (n - n)

=n * (ti1ti1 + ti2ti2 +… + tintin) - (ti1ti1 * 1 + ti2ti2 * 2 + … + tintin * n)

2、即相当于求 ti1ti1 * 1 + ti2ti2 * 2 + … + tintin * n 的最大值

3、假设ti1ti1 , ti2ti2 ,… , tintin是按自然顺序排好序时是最大值,即TmaxTmax = t1t1 * 1 + t2t2 * 2 + … + tntn

4、任意选择两项ta∗xta∗x,tb∗(x+c)tb∗(x+c),且tata < tbtb,c > 0,交换tata,tbtb位置得到tb∗xtb∗x,ta∗(x+c)ta∗(x+c) ,同时交换后不会对其他项造成影响

由于tata * x + tbtb * (x + c) = tata * x + tbtb * x + tbtb * c > tata * x + tbtb * x + tata * c = tbtb * x + tata * (x + c),即交换之后比原来的值更小.由于选取的任意性可得假设成立.

时间复杂度 O(nlogn)O(nlogn)

Java 代码

import java.util.*;
public class Main{
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int[] a = new int[n + 1];
    for(int i = 1;i <= n;i++)
    {
        a[i] = scan.nextInt();
    }
    Arrays.sort(a);
    long res = 0;
    for(int i = 1;i <= n;i++)
    {
        res += (a[i] * (n - i));
    }
    System.out.println(res);
}

}

算法分析

贪心决策

从前往后枚举每个区间,判断此区间能否将其放到现有的组中

如果一个区间的左端点比最小组的右端点要小,ranges[i].l<=heap.top() , 就开一个新组 heap.push(range[i].r);

如果一个区间的左端点比最小组的右端点要大,则放在该组, heap.pop(), heap.push(range[i].r);

每组去除右端点最小的区间,只保留一个右端点较大的区间,这样heap有多少区间,就有多少组。

算法流程

区间分组,在组内区间不相交的前提下,分成尽可能少的组。

而不是尽可能多的组,因为一个区间一组,就是尽可能多组的答案。

等效于把尽可能多的区间塞进同一组,要满足range[i].l > heap.top。

heap 存储的是每个组的最右的端点,由于是小根堆heap.top()是对应的最小的最右点。

那如果遇到,塞不进去的情况呢?

就是heap.top >= range[i].l, 当前区间的左端点比最小的右端点还要小,放到任何一组都会有相交部分。

那就需要新开一组,heap.push(range[i].r).

把所有区间按照左端点从小到大排序

从前往后枚举每个区间,判断此区间能否将其放到现有的组中

heap有多少区间,就有多少组

#include
#include
#include
#include
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];
int main()
{
scanf(“%d”, &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf(“%d%d”, &l, &r);
range[i] = {l, r};
}
sort(range, range + n);
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i ++ )
{
    if (heap.empty() || heap.top() >= range[i].l){
        heap.push(range[i].r);
    }
    else {
        heap.pop();
        heap.push(range[i].r);
    }
}
printf("%d\n", heap.size());
return 0;

}


相关文章
|
8天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
4月前
|
人工智能 算法
第一周算法设计与分析 G : 排队援救
这篇文章介绍了解决算法问题"排队援救"的方法,通过使用队列和映射来模拟救援点的排队过程,并确定最终得到救援的人的顺序和编号。
|
人工智能 算法
【贪心算法】排队打水
【贪心算法】排队打水
164 0
|
算法 调度
调度算法 | 先来先服务(超市排队结账模型)
在操作系统中,如何去衡量性能?我们先简化模型,只用一个性能指标去衡量——周转时间,周转时间的定义是任务完成时间减去任务到达系统的时间
183 0
|
3天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
110 80
|
21小时前
|
机器学习/深度学习 算法 索引
单目标问题的烟花优化算法求解matlab仿真,对比PSO和GA
本项目使用FW烟花优化算法求解单目标问题,并在MATLAB2022A中实现仿真,对比PSO和GA的性能。核心代码展示了适应度计算、火花生成及位置约束等关键步骤。最终通过收敛曲线对比三种算法的优化效果。烟花优化算法模拟烟花爆炸过程,探索搜索空间,寻找全局最优解,适用于复杂非线性问题。PSO和GA则分别适合快速收敛和大解空间的问题。参数调整和算法特性分析显示了各自的优势与局限。
|
22天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
28天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
16天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。

热门文章

最新文章