題目大意：
給出一個(gè)序列，長(zhǎng)度為N，均為正數(shù)。
找出一段連續(xù)的區(qū)間，此區(qū)間的平均值最大，長(zhǎng)度必須大于F。
好像還是有點(diǎn)實(shí)際用途的，這個(gè)問(wèn)題。
看完題之后，基本上就知道是做不出來(lái)的了。只想得到那種最簡(jiǎn)單的O(N^2)的解法，但是N = 100,000。這種解法必然超時(shí)。
在網(wǎng)上搜了兩個(gè)解題報(bào)告，發(fā)現(xiàn)此題的解法相當(dāng)牛逼！
兩種解法是完全不同類型的。
二分法
我們可以比較容易得出答案的最大值和最小值，即為序列中最大元素和最小元素。
二分法的關(guān)鍵在于判斷“一個(gè)可能的解跟正確答案相比是大了還是小了”。網(wǎng)上給的方法是：
如果要判斷val這個(gè)解，那就讓序列里所有元素的值都減去val。
然后試圖尋找一段連續(xù)的區(qū)間，該區(qū)間的長(zhǎng)度大于F，并且區(qū)間大于0。
可見(jiàn)，問(wèn)題一下轉(zhuǎn)化成統(tǒng)計(jì)數(shù)字的和，而不是數(shù)字的平均值，問(wèn)題變得明朗了。
尋找這種區(qū)間的算法是一個(gè)很簡(jiǎn)單的動(dòng)態(tài)規(guī)劃，復(fù)雜度為O(N)。
用 f[a, b] 表示在區(qū)間 [a, b] 中，所有子區(qū)間的最大值。
那么
當(dāng) b - a = F 時(shí)，f[a, b] 為序列中對(duì)應(yīng)的和。
當(dāng) b - a > F 時(shí)，f[a, b] = max{ f[a, b - 1] + arr[b], f[b - f + 1, b] }
我們要求的是 f[0, N]。
因此，二分法的復(fù)雜度是 O(NlgN)。代碼跑了接近300ms。
/**//*
* 代碼大量參考這份解題報(bào)告
* http://blog.sina.com.cn/s/blog_5c95cb070100dd47.html
* 原作者代碼寫(xiě)得很不錯(cuò)！贊一個(gè)！
*/
#include <stdio.h>
#define MAX_N 100032
double S[MAX_N], A[MAX_N];
int N, F;
int check(double val)
{
double cur, pre;
int i;
pre = S[F - 1] - val * (F - 1);
for (i = F; i <= N; i++) {
cur = S[i] - S[i - F] - val * F;
pre = pre + A[i] - val;
if (cur > pre)
pre = cur;
if (pre > -1e-6)
return 1;
}
return 0;
}
int main()
{
int i;
double l, r, m;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &F);
l = 1e50;
r = 0;
A[0] = S[0] = 0;
for (i = 1; i <= N; i++) {
scanf("%lf", &A[i]);
if (A[i] > r)
r = A[i];
if (A[i] < l)
l = A[i];
S[i] = S[i - 1] + A[i];
}
while (r - l >= 1e-6) {
m = (l + r) / 2;
if (check(m))
l = m;
else
r = m;
}
printf("%d\n", (int)(r * 1000));
return 0;
}
這個(gè)方法不是真的求點(diǎn)的凸包，是用了求凸包時(shí)候的技巧。
首先把序列轉(zhuǎn)化成一個(gè)圖，一共有N個(gè)點(diǎn)，第 i 個(gè)點(diǎn)的坐標(biāo)為 (i, S[i])，其中 S[i] 為序列的前 i 項(xiàng)和。
在圖上，能觀察到，點(diǎn)a點(diǎn)b之間的斜率就是區(qū)間[a, b]的平均值。
當(dāng) N = 6, F = 3 的時(shí)候，按照最簡(jiǎn)單的 O(N^2) 的做法，計(jì)算每?jī)蓚€(gè)點(diǎn)之間的斜率，計(jì)算的順序?yàn)椋?br>[1, 3]
[1, 4] [2, 4]
[1, 5] [2, 5] [3, 5]
[1, 6] [2, 6] [3, 6] [4, 6]
在算第6個(gè)點(diǎn)的時(shí)候，依次算了1，2，3，4跟點(diǎn)6的斜率。
為了避免不必要的計(jì)算，我們要沒(méi)必要計(jì)算的點(diǎn)剔除。
用類似凸包的計(jì)算更新方法，在點(diǎn)1，2，3。。。中維護(hù)一條“下凸折線”。
這樣，可以保證末尾的點(diǎn)跟折線中的點(diǎn)的斜率是先遞增再遞減的關(guān)系。
就能比較快的找出最大的斜率了。
這個(gè)算法的復(fù)雜度，網(wǎng)上的人說(shuō)是O(N)，但我覺(jué)得好像不是O(N)啊，也不知道是什么。
但是，絕對(duì)不能單單以復(fù)雜度來(lái)評(píng)價(jià)算法的啦。
代碼跑了150ms左右。比2分的還是快一點(diǎn)。
/**//*
* 思路參考此解題報(bào)告
* http://hi.baidu.com/ultramanzhy/blog/item/a8cb4efa1ecf2e1aa9d31123.html
* 解法牛逼！贊一個(gè)！
*/
#include <stdio.h>
#define MAX_N 100032
int S[MAX_N], stack[MAX_N], N, F, sp;
__inline int turn_right(int a, int b, int c)
{
int x1, y1, x2, y2;
x1 = b - a;
y1 = S[b] - S[a];
x2 = c - b;
y2 = S[c] - S[b];
return x1*y2 - x2*y1 <= 0;
}
__inline double calc_k(int a, int b)
{
return (double)(S[b] - S[a]) / (double)(b - a);
}
int main()
{
int i, j;
double max_val, val;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &F);
for (i = 1; i <= N; i++) {
scanf("%d", &j);
S[i] = S[i - 1] + j;
}
max_val = 0;
for (i = 0; i <= N - F; i++) {
while (sp >= 2 && turn_right(stack[sp - 2], stack[sp - 1], i))
sp--;
stack[sp++] = i;
for (j = sp;
j >= 2 && turn_right(stack[j - 2], stack[j - 1], i + F);
j--
);
val = calc_k(stack[j - 1], i + F);
if (val > max_val)
max_val = val;
}
printf("%d\n", (int)(max_val * 1000));
return 0;
}