题目描述：有一块长度为n的一维地，每格地可能为空('.')也可能有一只羊('*')
每次可以令一只羊左移或右移一格，当且仅当目的地是空。问最少几步能让这些羊相邻。

我的做法：记所有羊的坐标为ai,维护两个值f(x)=Σ|x-ai|，sum1[x]为x及之前的羊数，sum2[x]为x及之后的羊数，定义g(t)=t*(t-1)/2;
维护f(x)当x从0增至n-1时能做到O(1)计算；g(t)的目的是修正由于“羊不能重叠”而多算进去的步数。
发现记x∈[0,n-1]为目标点，那么步数ans=f(x)-g(sum1[x])-g(sum2[x]),取最小值即为答案。
这都什么垃圾想法复杂度O(Σ n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
ll a[1000010];
ll b[1000010];
ll f[1000010],l,r;
ll minmy(ll a,ll b) {return a>b?b:a;}
ll g(ll a) {return a*(a-1)/2;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t,n,cnt;
    ll ans;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s;
        cnt=0;ans=0;
        f[0]=0;
        for(int  i=0;i<n;++i)
        {
            if(s[i]=='*') ++cnt,f[0]+=i;
            a[i]=cnt;
        }
        cnt=0;
        for(int i=n-1;i>-1;--i)
        {
            if(s[i]=='*') ++cnt;
            b[i]=cnt;
        }

        r=a[n-1];l=0;

        for(int i=1;i<n;++i)
        {
            if(s[i-1]=='*') ++l,--r;
            f[i]=f[i-1]+l-r;
        }
        ans=f[0]-g(a[0])-g(b[0]);
        for(int i=1;i<n;++i)
        {
            ans=minmy(ans,f[i]-g(a[i])-g(b[i]));
            //cout<<f[i]<<' '<<a[i]<<' '<<b[i]<<endl;
        }
        cout<<ans<<endl;
    }
    //getchar();getchar();
    return 0;
}