POJ 1836

刚开始二分写错了 wa了很久 这个二分 的好好想想

#include <iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

using namespace std;

const double eps=1e-10;

double dp[2005],L[2005],R[2005];

int n;

int BIN(int len,double x)

{

    int left=0,right=len-1,mid;

    while(left<right)

        {

            mid=(left+right)/2;

            if(x>L[mid])left=mid+1;

            else  right=mid;

        }

        return left;

}

int work(int li,int ri)

{

	int i,gh=0,pos;

    L[0]=dp[0];

	int len=1,sum=0,KH=0;

    for(i=n-1;i>=ri;i--)

        R[KH++]=dp[i];

    for(i=1;i<li+1;i++)

    {

        if(dp[i]>L[len-1])

		{

          L[len++]=dp[i];

		}

        else

        {

             pos=BIN(len,dp[i]);

            L[pos] =dp[i];

        }

    }

    sum=li+1-len;

	gh=0;

    len=1;

    L[0]=R[0];

    for( i=1;i<KH;i++)

    {

        if(R[i]>L[len-1] )

		{

			L[len++]=R[i];

        }

		else

        {

             pos=BIN(len,R[i]);

             L[pos] =R[i];

        }

    }

    sum+=KH-len;

    return sum;

}

int main()

{

    int maxn,kk,i;

    while(scanf("%d",&n)==1)

        {

            maxn=1000000;

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

              scanf("%lf",&dp[i]);

            for( i=0;i<n-1;i++)

                if((kk=work(i,i+1))<maxn)maxn=kk;

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

        }

    return 0;

}

巴特西

POJ 1836

最新文章

热门文章