hdu3486Interviewe(二分是错的)(ST算法RMQ + 判定上下界枚举)

题目大意是找最小的m使得前m段中每一段的最大值相加严格大于k，每一段长度为[n/m]（n/m向下取整，多余的后半部分部分n-m*[n/m]不要）

先给一段我一开始的思路，和网上许多题解思路一样，但其实是有错误的。二分答案+RMQ (RMQ部分也可以用线段树)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + ;

const int inf = 0x3f3f3f3f;

int f[maxn][];

int n, k, m, v[maxn];

int mx, mi, tot;

inline int max( int a,int b ){

    return a>b ? a:b;

}

inline int min( int a, int b ){

    return a<b ? a:b;

}

inline void ST_make(){

    for( int i=; i<=n; i++ )

        f[i][] = v[i];

    for( int j=; (<<j)<=n; j++ )

        for( int i=; i<=n; i++ )

            f[i][j] = max( f[i][j-], f[i+(<<(j-))][j-] );

}

inline int ST_query( int l, int r ){

    int k = log(r-l+)/log();

    return max( f[l][k], f[r-(<<k)+][k]);

}

int main(){

    while( ~scanf("%d%d", &n, &k) ){

        if( n< && k< ) break;

        memset( f, , sizeof(f) );

        mx = -inf; mi = inf;

        tot = ;

        for( int i=; i<=n; i++ ){

            scanf("%d", &v[i]);

            tot += v[i];

            mx = max( v[i], mx );

            mi = min( v[i], mi );

        }

        if( mx>k ) {puts("1\n"); continue;}

        else if( tot<=k ) {puts("-1\n"); continue;}

        ST_make();

        mx = mx ? mx:;

        mi = mi ? mi:;

        int l = k/mx, r = min( n, k/mi+ ), sum;        //判断上下界，节省时间

        while( l<r ){

            sum = ;

            int mid = l+r>>;            //这个地方不能直接用m = l+r>>1

            int t = n/mid;

            int tmp = ;

            int d = t*mid;

            while( tmp<d){

                sum += ST_query( tmp, tmp+t- );

                tmp += t;

            }

            if( sum>k ){            //符合条件再令m = mid;

                r = mid;

                m = mid;

            }

            else l = mid+;

        }

        printf("%d\n", m);

    }

    return ;

}

思路都写好了，然鹅是错的。。。

给一份Discuss里dalao给的卡二分的数据

10 1500

1 1 1 1 1000 1000 1 1 1 1

很明显 答案是2 但是输出我记得好像是7

所以换了暴力枚举的思路，上代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + ;

const int inf = 0x3f3f3f3f;

int f[maxn][];

int n, k, m, v[maxn];

int mx, mi, tot;

inline int max( int a,int b ){

    return a>b ? a:b;

}

inline int min( int a, int b ){

    return a<b ? a:b;

}

inline void ST_make(){

    for( int i=; i<=n; i++ )

        f[i][] = v[i];

    int t = log(n)/log()+;

    for( int j=; j<t; j++ )

        for( int i=; i+(<<j)-<=n; i++ )

            f[i][j] = max( f[i][j-], f[i+(<<(j-))][j-] );

}

inline int ST_query( int l, int r ){

    int k = log(r-l+)/log();

    return max( f[l][k], f[r-(<<k)+][k]);

}

int main(){

    while( ~scanf("%d%d", &n, &k) ){

        if( n< && k< ) break;

        mx = -inf; mi = inf;

        tot = ;

        for( int i=; i<=n; i++ ){

            scanf("%d", &v[i]);

            tot += v[i];

            mx = max( v[i], mx );

            mi = min( v[i], mi );

        }

        if( tot<=k ){

            printf("-1\n");

            continue ;

        }

        ST_make();

        mx = mx ? mx:;

        mi = mi ? mi:;

        int l = k/mx, r = (k/mi+, n);        //判定上下界，节省时间(好像判了上界r还慢了。。)

        if(l==) l = ; 　　　　　　　　　　　　　　

        bool ok = ;

        for( m=l; m<=r; m++ ){

            int sum = ;

            int t = n/m;

            int d = t*m;

            for( int i=; i<=d; i+=t )            //这个地方要等于号，可举例n = m时 若i<d为判定条件则不能进行,卡了一年

                sum += ST_query( i, i+t- );

            if( sum>k ){

                ok = ;

                break;

            }

        }

        if(ok) printf("%d\n", m);

        else printf("-1\n");

    }

    return ;

}