奶牛题解

Calanosay · 2021-04-04 14:17:34 · 个人记录

为什么这题没有前缀和的题解qwq,前来填坑。

感觉就是裸逆序对的题，有木有？因为只有互相面对的奶牛才会必然减少产奶量，如果两头牛不是面对的话，比如11，可以先1号牛再2号牛，就可以零亏损了。因此这道题就是要求互相面对的奶牛，即求每个1后面有几个0。

下面上代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn],s[maxn];
int main(){
    int n;
    cin>>n;
    cin>>a[0];
    s[0]=a[0];
    for(int i=1;i<n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }//前缀和模板.... 
    long long ans=0;//long long一定要开 .
    for(int i=0;i<n;i++){
        if(a[i]==1){
            ans+=((n-1-i)-(s[n-1]-s[i]));//因为是前缀和 。
        }//sn代表的是有几个1，所以后面长度减去sn-si 。
    }//也就得出了有几个0。 
    cout<<ans;
}

听说之前黑题？CF官方评测1600分，个人感觉1200，普及-差不多吧。。还是有点太高了。