ZJU/ZOJ 2091 Mean of Subsequence 解题报告

题目大意是给出n个数，第一个人指定所选序列开始位置，第二个人指定序列长度，第一个人希望序列的平均值最大，第二个人希望序列的平均值最小，他们二人都足够聪明，求所选序列的平均值。

简单的说就是一道博弈问题，假定他们二人能够根据对方的最优决策来做出对自己最优的选择。设num[i]表示所给出的第i个数，posi[i]为取到最小均值时的结尾位置，avg[i,j]为a[i]到a[j]的均值。则有以下三个引理（证明略）：

1. 如果avg[i,j]<avg[j+1,k]，则avg[i,j]<avg[i,k]<avg[j+1,k]；如果avg[i,j]>avg[j+1,k]，则avg[i,j]>avg[i,k]>avg[j+1,k]。
2. 对于每个k(i<=k<posi[i])，必有avg[i,k]>=avg[k+1,posi[i]]。
3. 对于每个k(i<k<=posi[i])，必有posi[k]<=posi[i]

基于引理2和引理3，可以得到一种类似于我在ZJU/ZOJ 1985 解题报告中提到的迭代算法，求出每个位置开始的最小均值，从中选出一个最大的输出即可。但还有一种无论是编程复杂度、时间复杂度、空间复杂度还是思维复杂度都更优的贪心算法。计算从第i(1<=i<=n)位到第n位组成的序列的均值，其中的最大值即为所求。

证明：设第m位到第n位为求出的最大均值序列。

由引理2可证明，假设以num[m]开头的最小均值序列的结尾不是num[n]，而是num[k]，则avg[k+1,n]>avg[m,k]，则以num[n]结尾的最大均值序列的开头是k+1而不是m，矛盾。

当i<m时，必有avg[i,n]<avg[m,n]。这个由m的定义即可得知。由引理2可证明，当i>m时，均有avg[i,n]<avg[m,n]。

3005960 2008-07-26 11:17:10 Accepted 2091 FPC 00:00.12 412K IwfWcf@LZOI