题目
对于每一个位置，统计一下它移到上升那边和下降那边分别需要多少次，然后贪心取个最小值，就可以了。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<vector> #include<cmath> #include<map> #include<string> #include<queue> #include<stack> #include<bitset> #include<list> #include<set> #include<utility> #include<functional> #include<iomanip> #define IO ios::sync_with_stdio(false) #define eps 1e-7 #define int long long using namespace std; int c[100005]={0},a[100005],n,l[100005],r[100005]; void add(int pos,int val) { for(;pos<=100003;pos+=pos&-pos) { c[pos]+=val; } } int ask(int pos) { int anss=0; for(;pos;pos-=pos&-pos) { anss+=c[pos]; } return anss; } signed main() { IO; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { add(a[i],1); l[i]+=ask(100003)-ask(a[i]); } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--) { add(a[i],1); r[i]+=ask(100003)-ask(a[i]); } int ans=0; for(int i=1;i<=n;i++) { ans+=min(l[i],r[i]); } cout<<ans; }