区间问题
区间选点
给定N个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数N,表示区间数。
接下来N行,每行包含两个整数ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
//这个题和LeetCode第435题无重叠区间思想是一样的 func pointSelect(intervals [][]int) int{ if len(intervals) == 0 || len(intervals[0]) == 0{ return 0 } sort.Slice(intervals,func(i,j int)bool{ return intervals[i][1] < intervals[j][1] }) n := len(intervals) res,r := 1,intervals[0][1] for i := 1 ; i < n ; i++ { if intervals[i][0] > r { res ++ r = intervals[i][1] } } return res }
最大不相交区间数量
给定N个闭区间[ai,bi],请你在数轴上选择若干个区间,使得选中的区间之间互不相交(包括端点),输出可选区间的最大数量
func maxInterval(intervals [][]int) int{ if len(intervals) == 0 || len(intervals[0]) == 0{ return 0 } sort.Slice(intervals,func(i,j int)bool{ return intervals[i][1] < intervals[j][1] }) n := len(intervals) res,r := 1,intervals[0][1] for i := 1 ; i < n ; i++ { if intervals[i][0] > r { res ++ r = intervals[i][1] } } return res }
区间分组
给定N个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并且使得组数尽可能小
大家可以把这个问题想象成活动安排问题
有若干个活动,第i个活动开始时间和结束时间是[Si,fi],同一个教室安排的活动之间不能交叠,求要安排所 有活动,最少需要几个教室?
有时间冲突的活动不能安排在同一间教室,与该问题的限制条件相同,即最小需要的教室个数即为该题答案。
我们可以把所有开始时间和结束时间排序,遇到开始时间就把需要的教室加1,遇到 结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中,峰值就是多同时进行的活动数,也是我们至少需要的教室数。
func groupByInterval(intervals [][]int) int { n := len(intervals) if n == 0 || len(intervals[0])==0 { return 0 } var temp []int for i := 0 ; i < n ; i++ { temp = append(temp,intervals[i][0]*2) temp = append(temp,intervals[i][1]*2 + 1) } sort.Ints(temp) res,t := 1,0 for i := 0 ; i < len(temp) ; i++ { if t % 2 == 0 { t++ }else{ t-- } res = max(res,t) } return res }
区间覆盖
给定N个闭区间[ai,bi]以及一个线段区间[s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。输出最少的区间数,如果无法完全覆盖则输出-1
func intervalCoverage(intervals [][]int,start int,end int) int{ n := len(intervals) if n == 0 || len(intervals[0])==0 { return -1 } sort.Slice(intervals,func(i,j int)bool{ return intervals[i][0] < intervals[j][0] }) res := 0 success := false for i := 0 ; i < n ; i++ { j := i r := -2e9 for j < n && intervals[j][0] <= start{ r := max(r,intervals[j][1] j++ } if r < start { res = -1 break } res ++ if r >= end{ success = true break } start = r i = j-1 } if !success {res = -1} return res }
哈夫曼树
合并果子
在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。
可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体力最少,并输出这个最小的体力耗费值。
例如有3种果子,数目依次为1,2,9。
可以先将1、2堆合并,新堆数目为3,耗费体力为3。
接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。
所以达达总共耗费体力=3+12=15。
可以证明15为最小的体力耗费值。
输入格式
输入包括两行,第一行是一个整数n,表示果子的种类数。
第二行包含n个整数,用空格分隔,第i个整数ai是第i种果子的数目。
输出格式
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。
输入数据保证这个值小于231。
数据范围
1≤n≤100001≤n≤10000
1≤ai≤200001≤ai≤20000
样例
输入样例:
3
1 2 9
输出样例:
15
#include <iostream> #include <algorithm> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); priority_queue<int, vector<int>, greater<int>> heap; while (n -- ) { int x; scanf("%d", &x); heap.push(x); } int res = 0; while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); res += a + b; heap.push(a + b); } printf("%d\n", res); return 0; }
排序不等式
排队打水
n个人排队到1个水龙头处打水,第i个人装满水桶所需要的时间是ti,请问如何安排他们的打水顺序才能使得所有人的等待时间之和最小?
//直接按照打水时间从小到大排序,这样就能保证所有人的等待之和最小 func waitingForWater(line []int) int{ n := len(line) sort.Ints(line) res := 0 for i := 0 ; i < n ; i++{ res += line[i]*(n-i-1) } return res }
绝对值不等式
货仓选址
在一个数轴上有n家商店,它们的坐标分别是A1-An。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品,为了提高效率,求把货仓建在哪里,可以使得货仓到每家商店的距离之和最小
func selecctAddress(store []int) int{ n := len(store) sort.Ints(store) res := 0 for i := 0 ; i < n ; i++{ res += abs(store[i]-store[n/2]) } return res } func abs(a,b int)int{ if a-b > 0 { return a-b } return b-a }
推公式
耍杂技的牛
农民约翰的N头奶牛(编号为1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。
奶牛们不是非常有创意,只提出了一个杂技表演:
叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。
一头牛只撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小
//按照wi+si从小到大的顺序排序,最大的危险系数一定是最小的,这个排序是最优的 func cow(w []int,s []int){ res := -2e9 sum := 0 for i := 0 ; i < n ; i++ { res = max(res,sum-s[i]) sum += w[i] } return res }