8
7
4
8
10
1
2
6
9
7
就是让你通过交换两两相邻的数字然后达到序列是先递增后递减的状态（可以只递增/减）
这个我们首先可以确定最大值即峰值的数值是一定的，但是位置不确定
如果考虑最小值的话，不仅数值是确定的，位置也是确定的，在左右两侧
具体是移动到左边还是移动到右边，这里就可以采用贪心的策略，如果距离左边近，就移动到左边，否则移动到右边
具体操作：
可以用map记录每个数字的初始位置，然后看看维护一个l=1,r=n，如果移动到l的位置，就l++，r同理
如果一个数字的真实位置是pos1，初始位置是pos2
如果他移动到左边的去
那么原区间[1,pos-1]的下标值全部加一，这里我们用树状数组维护就好了
CODE：
ll n,a[maxn]; map<ll,ll>mp; priority_queue<ll,vector<ll>,greater<ll> >q; ll ans,t[maxn]; ll lowbit(ll x) { return x&(-x); } void add(ll x,ll num) { while(x<=n) t[x]+=num,x+=lowbit(x); } ll qq(ll x) { //if(x==0) return 0; ll ans=0; while(x>0) { ans+=t[x]; x-=lowbit(x); } return ans; } int main() { n=read(); rep(i,1,n) a[i] = read(),q.push(a[i]),mp[a[i]] = i,add(i,i),add(i+1,-i); int l =1 ,r = n; //如果移动到左右两侧，对应的位置在哪 while(q.size()) { int x = q.top(); q.pop(); x = mp[x]; int pos = qq(x) ; //真实位置 int L = pos - l; int R = r-pos; // cout<<pos<<endl; if(L<=R) { //移动到左边 //移动到l ans+=L; add(1,1); add(x,-1); l++; } else { //移动到右边 //移动到r ans+=R; add(x+1,-1); r--; } } out(ans); return 0; }
ICPC Southeast USA 2020 Regional Contest proble C: Bitonic Ordering（贪心）
原文：https://www.cnblogs.com/UpMing/p/14646390.html