洛谷P3608 [USACO17JAN]Balanced Photo平衡的照片

题目描述

Farmer John is arranging his $h_ihi, and the heights of all cows are distinct.$

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow $L_iLi and R_iRi differ by more than factor of 2, where L_iLi and R_iRi are the number of cows taller than ii on her left and right, respectively. That is, ii is unbalanced if the larger of L_iLi and R_iRi is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.$

Please help FJ compute the total number of unbalanced cows.

FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。

就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果L[i]和R[i]的数目相差2倍以上的话，第i头奶牛就是不平衡的。（L[i]和R[i]分别代表第i头奶牛左右两边比她高的数量）。如果L[i]和R[i]中较大者比较小者的数量严格多两倍的话，这头奶牛也是不平衡的。FJ不希望他有太多的奶牛不平衡。

请帮助FJ计算不平衡的奶牛数量。

输入输出格式

输入格式：

The first line of input contains $h_1 ldots h_Nh1…hN, each a nonnegative integer at most 1,000,000,000.$

第一行一个整数N。接下N行包括H[1]到H[n]，每行一个非负整数（不大于1,000，000，000)。

输出格式：

Please output a count of the number of cows that are unbalanced.

请输出不平衡的奶牛数量。

输入输出样例

输入样例#1：

输出样例#1：

#include<cstdio>    
#include<algorithm>    
#include<iostream>    
#include<queue>    
#include<cstring>
using namespace std;    
const int maxn=100009;    
int n,a[maxn],b[maxn];    
int l[maxn],r[maxn],f[maxn];    
inline int lowbit(int x){    
    return x&-x;    
}    
inline void add(int x){    
    for(;x<=n;x+=lowbit(x))    
        f[x]++;    
}    
inline int sum(int x){    
    int ans=0;    
    for(;x;x-=lowbit(x))    
        ans+=f[x];    
    return ans;    
}    
int main(){    
    scanf("%d",&n);    
    for(int i=1;i<=n;i++)    
        scanf("%d",&a[i]),b[i]=a[i];    
    sort(b+1,b+n+1);    
    for(int i=1;i<=n;i++)    
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;    
    for(int i=1;i<=n;i++)    
        l[i]=i-1-sum(a[i]),add(a[i]);//正着找逆序对    
    memset(f,0,sizeof(f));    
    for(int i=n;i;i--)    
        r[i]=n-i-sum(a[i]),add(a[i]);//倒着找正序对    
    int ans=0;    
    for(int i=1;i<=n;i++){    
        if(l[i]==0&&r[i]==0) continue;    
        if(!l[i]||!r[i]) ans++;    
        else{    
            int xx=max(l[i],r[i]),yy=min(l[i],r[i]);    
            if(xx/yy>2) ans++;    
            else if(xx/yy==2&&yy*2!=xx) ans++;    
        }    
    }    
    printf("%d",ans);    
    return 0;    
}

#include<cstdio>    
#include<algorithm>    
#include<iostream>    
#include<queue>    
#include<cstring>
using namespace std;    
const int maxn=100009;    
int n,a[maxn],b[maxn];    
int l[maxn],r[maxn],f[maxn];    
inline int lowbit(int x){    
    return x&-x;    
}    
inline void add(int x){    
    for(;x<=n;x+=lowbit(x))    
        f[x]++;    
}    
inline int sum(int x){    
    int ans=0;    
    for(;x;x-=lowbit(x))    
        ans+=f[x];    
    return ans;    
}    
int main(){    
    scanf("%d",&n);    
    for(int i=1;i<=n;i++)    
        scanf("%d",&a[i]),b[i]=a[i];    
    sort(b+1,b+n+1);    
    for(int i=1;i<=n;i++)    
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;    
    for(int i=1;i<=n;i++)    
        l[i]=i-1-sum(a[i]),add(a[i]);//正着找逆序对    
    memset(f,0,sizeof(f));    
    for(int i=n;i;i--)    
        r[i]=n-i-sum(a[i]),add(a[i]);//倒着找正序对    
    int ans=0;    
    for(int i=1;i<=n;i++){    
        if(l[i]==0&&r[i]==0) continue;    
        if(!l[i]||!r[i]) ans++;    
        else{    
            int xx=max(l[i],r[i]),yy=min(l[i],r[i]);    
            if(xx/yy>2) ans++;    
            else if(xx/yy==2&&yy*2!=xx) ans++;    
        }    
    }    
    printf("%d",ans);    
    return 0;    
}