【贪心+权值线段树】代码源每日一题div1 双端队列
感觉难度不如蓝桥杯
题意:
思路:
手摸几个样例可以发现,不管怎么放,最小贡献是确定的
因此可以直接计算最小贡献
遍历数组,直接算两种决策的逆序对数的最小值就行了
当然需要离散化一下
还有为了防止线段树越界,要和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<< ; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int __=1;//cin>>__; while(__--)solve();return 0; }