TIOJ 1237 砍了那些腳 Cut Many Legs [Greedy]

poao899    15648K    2009MS    G++     0.76K     2010-03-27 15:44:35                                .

同UVa 10291不過測資加大(50 →  2*10^6)


是說這題題目頗難懂Q

以下是解釋小心雷

//***************************************

一個桌子會傾斜，就是因為把兩個平衡又高的腳連線當支點，

其中有一邊全部都是短腳而且佔其他所有桌腳重量一半( >= floor( (n-1)/2 ) )

Ex 1:

7
3 3 1 1 3 1 1
平衡 所以0

Ex 2:

6
3 1 1 3 3 3
不平衡所以全部砍到剩下1，答案是8

也就是找到一個數字是k，讓數列不能有連續(n-1)/2個數字小於k

//***************************************

#include<stdio.h>
int leg[4000010],n;
int l,r,mid,limit;
long long cut;
bool test(){
    int s=0;
    for(int i=0;i<n*2;i++){
        s++;
        if(leg[i]>mid)s=0;
        if(s>=limit)return 0;
    }
    return 1;
}
int getint(){
    int g=0,c=getchar(),s=1;
    while(c==32||c==10||c==9)c=getchar();
    if(c=='-'){s=-1;c=getchar();}
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g*s;
}
int main(){
    while(n=getint()){
        l=2147483647;r=-214748364;cut=0;
        limit=(n-1)/2;
        for(int i=0;i<n;i++){
            leg[i+n]=leg[i]=getint();
            if(leg[i]>r)r=leg[i];
            if(leg[i]<l)l=leg[i];
        }
        while(l!=r){
            mid=(l+r)/2;
            if(test())l=mid+1;
            else r=mid;
        }
        for(int i=0;i<n;i++)
            if(leg[i]>l)cut+=leg[i]-l;
        printf("%lld\n",cut);
    }
}