糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 2018 Best Cow Fences 牛题

题目大意:
给出一个序列,长度为N,均为正数。
找出一段连续的区间,此区间的平均值最大,长度必须大于F。

好像还是有点实际用途的,这个问题。
看完题之后,基本上就知道是做不出来的了。只想得到那种最简单的O(N^2)的解法,但是N = 100,000。这种解法必然超时。

在网上搜了两个解题报告,发现此题的解法相当牛逼!
两种解法是完全不同类型的。

二分法
我们可以比较容易得出答案的最大值和最小值,即为序列中最大元素和最小元素。
二分法的关键在于判断“一个可能的解跟正确答案相比是大了还是小了”。网上给的方法是:
如果要判断val这个解,那就让序列里所有元素的值都减去val。
然后试图寻找一段连续的区间,该区间的长度大于F,并且区间大于0。
可见,问题一下转化成统计数字的和,而不是数字的平均值,问题变得明朗了。
寻找这种区间的算法是一个很简单的动态规划,复杂度为O(N)。
用 f[a, b] 表示在区间 [a, b] 中,所有子区间的最大值。
那么
当 b - a = F 时,f[a, b] 为序列中对应的和。
当 b - a > F 时,f[a, b] = max{ f[a, b - 1] + arr[b], f[b - f + 1, b] }

我们要求的是 f[0, N]。
因此,二分法的复杂度是 O(NlgN)。代码跑了接近300ms。


/*
 *    代码大量参考这份解题报告
 *    
http://blog.sina.com.cn/s/blog_5c95cb070100dd47.html
 *    原作者代码写得很不错!赞一个!
 
*/

#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;
}



凸包法
这个方法不是真的求点的凸包,是用了求凸包时候的技巧。
首先把序列转化成一个图,一共有N个点,第 i 个点的坐标为 (i, S[i]),其中 S[i] 为序列的前 i 项和。
在图上,能观察到,点a点b之间的斜率就是区间[a, b]的平均值。
当 N = 6, F = 3 的时候,按照最简单的 O(N^2) 的做法,计算每两个点之间的斜率,计算的顺序为:
[1, 3]
[1, 4] [2, 4]
[1, 5] [2, 5] [3, 5]
[1, 6] [2, 6] [3, 6] [4, 6]
在算第6个点的时候,依次算了1,2,3,4跟点6的斜率。
为了避免不必要的计算,我们要没必要计算的点剔除。
用类似凸包的计算更新方法,在点1,2,3。。。中维护一条“下凸折线”。
这样,可以保证末尾的点跟折线中的点的斜率是先递增再递减的关系。
就能比较快的找出最大的斜率了。
这个算法的复杂度,网上的人说是O(N),但我觉得好像不是O(N)啊,也不知道是什么。
但是,绝对不能单单以复杂度来评价算法的啦。
代码跑了150ms左右。比2分的还是快一点。

/*
 *    思路参考此解题报告
 *    
http://hi.baidu.com/ultramanzhy/blog/item/a8cb4efa1ecf2e1aa9d31123.html
 *    解法牛逼!赞一个!
 
*/

#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;
}


posted on 2010-03-02 20:52 糯米 阅读(3203) 评论(3)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 2018 Best Cow Fences 牛题[未登录]  回复  更多评论   

有On算法,代码只有30行
2010-03-22 13:42 | 123

# re: POJ 2018 Best Cow Fences 牛题  回复  更多评论   

@123
哥们,能贴代码上来不?谢啦!
2010-03-29 13:47 | 糯米

# re: POJ 2018 Best Cow Fences 牛题  回复  更多评论   

写的不错,简洁易懂,适合我这种菜鸟
2011-09-26 20:51 | 天青色~~

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理