joi春合宿2014 day1-2:Growing Vegetables is Fun

問題文

http://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d1.pdf

解法

しばらくBITとかを用いた嘘解法で戦ってて、嘘を嘘じゃなくすると満点が取れないことに気付いて絶望するなどした。

よく考えたら短いやつから順に貪欲的に端に寄せていけばいいと分かったのでBITとか使いながらやったら通った。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct BIT{
    int N;
    vector<int>dat;

    void init(int n){
        N=n;
        dat.resize(N+1,0);
    }

    void add(int k,int x){
        k++;
        while(k<=N){
            dat[k]+=x;
            k+=k&-k;
        }
    }

    int getSum(int k){
        k++;
        int ret=0;
        while(k){
            ret+=dat[k];
            k-=k&-k;
        }
        return ret;
    }
};


int N;
int D[300000];
vector<int>hs;
vector<int>v[300000];

int mincost(BIT &bit,vector<int>&vec){
    int ret=0;
    for(int i=0;i<vec.size();i++){
        int l=(vec[i]-bit.getSum(vec[i]))-i;
        int r=N-1-vec[i]-(bit.getSum(N)-bit.getSum(vec[i]))-(vec.size()-1-i);
        ret+=min(l,r);
    }

    for(int i=0;i<vec.size();i++)bit.add(vec[i],1);
    return ret;
}

signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    //input
    cin>>N;
    for(int i=0;i<N;i++)cin>>D[i];

    
    //compress
    for(int i=0;i<N;i++)hs.push_back(D[i]);
    sort(hs.begin(),hs.end());
    hs.erase(unique(hs.begin(),hs.end()),hs.end());
    for(int i=0;i<N;i++){
        D[i]=lower_bound(hs.begin(),hs.end(),D[i])-hs.begin();
    }
    
    //solve
    for(int i=0;i<N;i++){
        v[D[i]].push_back(i);
    }

    int ans=0;
    BIT bit;
    bit.init(N+100);

    for(int i=0;i<N;i++){
        if(v[i].size()==0)continue;
        ans+=mincost(bit,v[i]);
    }
    cout<<ans<<endl;
}