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

作法：

因為桌子平衡會等價於「圓心嚴格落在最長的桌腳們形成的多邊形內部」，所以只要二分「和地面接觸的桌腳長度(超過的就是被砍掉的)」，然後判斷有沒有相鄰的桌腳跨越了整個圓的一半就OK了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 2147483647
using namespace std;
const int maxn=2000000+10 ;
 
int n,a[maxn] ;
 
bool check(int x)
{
    int fir=-1,last=-1 ;
    for(int i=0;i<n;i++) if(a[i]>=x)
    {
        if(fir==-1) { fir=last=i ; continue ; }
        if(i-last >= (n+1)/2) return 0 ;
        last=i ;
    }
    if( fir-last+n >= (n+1)/2 ) return 0 ;
    return 1 ;
}
 
main()
{
    scanf("%d",&n) ;
    int l=INF , r=0 ;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]) ,
        l=min(l,a[i]) , r=max(r,a[i]) ;
    r++ ;
    while(r-l>1)
    {
        int mid=l+(r-l)/2 ;
        if(check(mid)) l=mid ;
        else r=mid ;
    }
    LL ans=0LL ;
    for(int i=0;i<n;i++) ans+=max(0LL,(LL)a[i]-l) ;
    printf("%lld\n",ans) ;
}