排队打水算法实现

算法分析

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

证明：

不妨设

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

}