【题解】最大平均数(二分区间求最大子段和)
[collapse title="题目描述"] 已知n个整数A1、A2、...、An,从中找出一个连续区间Ai到Aj,使得该区间的数字个数不小于m,且区间内数字的平均值最大。(在计算平均值时,如果不为整数,那么以该值向下取整作为平均值) 求这个最大区间平均值。 输入多组案例。一个正整数T,表示案例的数量。(T<=100) 每组案例中,先是两个…
蓝桥杯一日游(试题E:路径 题解)
昨天第一次参加蓝桥杯,就遇到了史上最难的题目!之前听学长说暴力杯拿奖很容易,还有学分拿,就动心了!没想到暴力杯一去不复返~~搭进去300块钱,罚坐四小时。出来一对答案,估计拿了不到40分(太羞耻了) ...
对极值问题的探索
1.三分法 在对区间做二分查找之前,我们要保证这个区间是有序的,二分法适用于单调函数。对于非单调函数,二分法就不适用了,需要使用一种新的方法——三分法。 三分法首先把待求区间分成三份 mid1=L+(R-L)/3 mid2=R-(R-L)/3 比较f(mid1)和f(mid2)谁更靠近极值,若f(mid1)更靠近极值,则将右区间改为mid2,若f(…