【贪心+权值线段树】代码源每日一题div1 双端队列

桃扇骨 2024-03-16 16:49 53阅读 0赞

**感觉难度不如蓝桥杯**

[双端队列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![879b16213e1b43a6a486cae04fa6de59.png][]

思路：

手摸几个样例可以发现，不管怎么放，最小贡献是确定的

![7542aa0823604c23b4db4edbd0d36421.jpeg][]

因此可以直接计算最小贡献

遍历数组，直接算两种决策的逆序对数的最小值就行了

当然需要离散化一下

还有为了防止线段树越界，要和1取max，和N取min

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int val;
    }tree[mxe<<2];
    
    int N,tot=0;
    int a[mxn],b[mxn];
    
    void pushup(int rt){
        tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void modify(int rt,int l,int r,int x,int k){
        if(l==r){
            tree[rt].val+=k;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,k);
        else modify(rt<<1|1,mid+1,r,x,k);
        pushup(rt);
    }
    int query(int rt,int l,int r,int x,int y){
        int res=0;
        if(x<=l&&r<=y){
            return tree[rt].val;
        }
        int mid=l+r>>1;
        if(x<=mid) res+=query(rt<<1,l,mid,x,y);
        if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y);
        return res;
    }
    void build(int rt,int l,int r){
        if(l==r){
            tree[rt].val=0;
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            b[++tot]=a[i];
        }
        sort(b+1,b+1+tot);
        int len=unique(b+1,b+1+tot)-b-1;
        int ans=0;
        build(1,1,N);
        for(int i=1;i<=N;i++){
            int u=a[i];
            int v=lower_bound(b+1,b+1+len,u)-b;
            int res1=query(1,1,N,min(v+1,N),N);
            int res2=query(1,1,N,1,max(v-1,1ll));
            ans+=min(res1,res2);
            modify(1,1,N,v,1);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/1004
[879b16213e1b43a6a486cae04fa6de59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cfe0f567117643329b76b64b29543307.png
[7542aa0823604c23b4db4edbd0d36421.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/72b1b7a9951a4a109a555aeb7ba1cde7.png