排队打水算法实现

简介: 排队打水算法实现

算法分析

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

证明:

不妨设

(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;

}


相关文章
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
5月前
|
算法 搜索推荐 测试技术
【调度算法】快速非支配排序算法
【调度算法】快速非支配排序算法
46 3
|
3月前
|
人工智能 算法
第一周算法设计与分析 G : 排队援救
这篇文章介绍了解决算法问题"排队援救"的方法,通过使用队列和映射来模拟救援点的排队过程,并确定最终得到救援的人的顺序和编号。
|
5月前
|
算法 调度
【调度算法】关于轮盘赌和锦标赛两种选择算子的选用思考
【调度算法】关于轮盘赌和锦标赛两种选择算子的选用思考
112 1
|
11月前
|
人工智能 图形学
UnityAI——排队过窄洞
UnityAI——排队过窄洞
UnityAI——排队过窄洞
|
Java
java数据结构31:银行业务队列简单模拟
设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍---即当A窗口处理完2个顾客时,B窗口处理完一个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。
194 0
|
算法 安全
秒懂算法 | 银行家算法
最具有代表性的避免死锁的算法是Dijkstra的银行家算法,由于该算法可能用于银行现金贷款而得名。一个银行家把他的固定资金贷给若干顾客,只要不出现一个顾客借走所有资金后还不够,银行家的资金应是安全的。银行家需要一个算法保证借出去的资金在有限时间内可以收回。 假定顾客分成若干次进行贷款,并在第一次贷款时说明他的最大借款额。具体算法如下:
308 0
秒懂算法 | 银行家算法
|
调度
L2-014 列车调度 (25 分)(二分)
L2-014 列车调度 (25 分)(二分)
178 0
L2-014 列车调度 (25 分)(二分)