还是膜网上题解QAQ
从低到高考虑，这样就不会影响后挪的草了。
每次把草贪心地挪到代价较小的一边。位置为i的草，花费为min( 1..i-1中更高的草的数目，i+1..n中更高的草的数目 )
因为更小的草已经被挪到两边了..所以代价就是更高的草的数目。
拿个树状数组统计一下就好了。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #define ll long long 6 using namespace std; 7 const int maxn=300002; 8 struct zs{int v,id;}a[maxn]; 9 int mp[maxn],t[maxn],t1[maxn]; 10 ll ans; 11 int i,j,k,n,m,cnt; 12 13 int ra;char rx; 14 inline int read(){ 15 rx=getchar(),ra=0; 16 while(rx<'0'||rx>'9')rx=getchar(); 17 while(rx>='0'&&rx<='9')ra=ra*10+rx-48,rx=getchar();return ra; 18 } 19 bool cmp(zs a,zs b){return a.v<b.v;} 20 int main(){ 21 n=read();register int j;int x,y; 22 for(i=1;i<=n;i++)a[i].v=read(),a[i].id=i; 23 sort(a+1,a+1+n,cmp); 24 for(i=1;i<=n;mp[a[i].id]=cnt,i++)cnt+=a[i].v!=a[i-1].v; 25 for(i=1;i<=n;i++){ 26 j=mp[i];while(j<=cnt)t1[j]++,j+=j&-j; 27 } 28 for(i=n;i>1;i--){ 29 j=mp[i];while(j<=cnt)t1[j]--,j+=j&-j; 30 x=n-i,y=i-1; 31 j=mp[i];while(j)x-=t[j],y-=t1[j],j-=j&-j; 32 ans+=x<y?x:y; 33 j=mp[i];while(j<=cnt)t[j]++,j+=j&-j; 34 } 35 printf("%lld\n",ans); 36 }