題意：現在要給站成一排的n頭牛擠奶，每頭牛都要麼面朝左要麼面朝右。在給一頭牛A擠奶的時候，未被擠奶并且面朝A的所有奶牛都會受到驚吓而奶品質降1，可以認為每頭牛的奶品質足夠大（每次都夠減）。問選擇最佳的擠奶順序使得總品質損失最小，輸出最小的損失量。
解法：就是一道思維題，可以這樣了解。我們把一個沖突對定義為頭對頭兩頭牛，他倆一個向右另一個向左并且互相看到對方。那麼僅僅對這一對來說，無論順序如何，品質都會損失1，不會多也不會少。對于非沖突對的向左向右的兩頭牛，無論順序如何，品質都不會有損失。也就是說，對于向左的牛來說，無論向右牛擠奶順序如何，都不會有什麼差別，反之一樣。然後再看，在所有向左的奶牛中，一定是從右向左擠為最佳順序，在所有向右的奶牛中，一定是從左向右擠為最佳順序。是以，現在結論就出來了：從左向右，将所有面朝右的奶牛擠了，這時所有的損失等于将每頭面朝右奶牛左邊面朝左的奶牛的數量加起來。然後再從從右向左，将所有面朝左的奶牛擠了，這期間的品質損失是0.代碼超短。但是自己在比賽時候沒有想到這些，搞了半天YY了個nlogn樹狀數組亂搞的；100行代碼，wa了兩發，最後一分鐘才補交正确通過。悼念一下我那逗比的YY代碼吧:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int C1[200010];
int C2[200010];
int n;
int lowbit(int x)
{
return x&(-x);
}
void update1(int x)
{
while(x<=n)
{
C1[x]++;
x+=lowbit(x);
}
}
int query1(int x)
{
int ans=0;
while(x)
{
ans+=C1[x];
x-=lowbit(x);
}
return ans;
}
void update2(int x)
{
while(x<=n)
{
C2[x]++;
x+=lowbit(x);
}
}
int query2(int x)
{
int ans=0;
while(x)
{
ans+=C2[x];
x-=lowbit(x);
}
return ans;
}
bool rem[200010];
struct point
{
int num,position;
bool de;
} ;
point points[200010];
bool operator<(point a,point b)
{
return a.num<b.num;
}
int num[200010];
int sum1[200010];
int sum2[200010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>rem[i];
if(rem[i])num[i]=n-i,sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1];
else num[i]=i-1,sum1[i]=sum1[i-1],sum2[i]=sum2[i-1]+1;
points[i].num=num[i],points[i].position=i;
points[i].de=rem[i];
}
sort(points+1,points+n+1);
reverse(points+1,points+n+1);
long long ans=0;
int left=0,right=0;
for(int i=1;i<=n;i++)
{
int k=points[i].position;
if(rem[points[i].position])
update2(points[i].position);
else
update1(points[i].position);
if(rem[points[i].position])right++;
else left++;
}
cout<<ans<<endl;
return 0;
} int tool1=query1(points[i].position-1);
int tool2=query2(points[i].position-1);
ans+=sum1[k-1]-tool2+sum2[n]-sum2[k]-(left-tool1);
if(rem[points[i].position])
right++;
else
left++;
}
cout<<ans<<endl;
return 0;
}