算法分析
安排他们的打水顺序才能使所有人的等待时间之和最小,则需要将打水时间最短的人先打水
证明:
不妨设
(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;
}