补题 10.2模拟 T2 序列交换

B. 序列交换

给定一个长度为 n 的序列 a，你最少需要多少次“交换相邻两项”的操作，才能满足这个序列先（非严格）增后（非严格）减。

形式化地说，即存在一个 k\in \{1,2,\dots,n\}，使得 a_1 \le a_2 \le \cdots \le a_k \ge a_{k+1} \ge \cdots \ge a_n。注意允许取 k=1 或 k=n 的情况，此时分别相当于 a_1 \ge a_2 \ge \cdots \ge a_n 或者 a_1 \le a_2 \le \cdots \le a_n。

对于 100% 的数据：2 \le n \le 3\times10^5,\ \ 1 \le a_i \le n。

思路分析

考虑构造一个符合题意的序列，从大到小遍历序列，每次可以选择将数放到左边或者右边，不难证明均符合题意。考虑将原序列变形的交换代价，每次交换将代价计算到较小的数上，最终代价即为所有数代价之和。因此把一个数放到左边的代价就是左边比这个数大的的个数，放到右边亦然。下给出一个形式上的证明：

取 x\in L ，考虑 \forall \ y: y > x 在序列中的位置：

y \in L 时，要满足 L 内单调非降，则 y 一定要在 x 右侧。
y\in R 时，显然 y 在 x 右侧。

因此所有大于 x 的数最终都应该在右侧，当原序列中存在形如 (y,x) 这样的逆序对时，只需要一次交换即可消除，因此将一个数放到左边的代价只需统计左边比这个数大的数的个数。

当取 x\in R 时，与上述情况同理，不重复说明。

因此只需考虑每个数左边比这个数大的个数或者右边比这个数大的个数，取其中较小的，最后求和即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+9;
int n;
int a[maxn],b[maxn];
int bit[maxn],l[maxn]; // l[i]代表i左边有几个比i大的
int lowbit(int x){
    return x&(-x);
}
void add(int i){
    for(;i<=n;i+=lowbit(i)) bit[i]+=1;
}
int query(int i){
    int res=0;
    for(;i>0;i-=lowbit(i)) res+=bit[i];
    return res;
}
ll pref[maxn],suf[maxn];
int main(){
	// freopen("swap.in","r",stdin);
	// freopen("swap.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    for(int i=1;i<=n;i++){
    	l[i]=i-1-query(a[i]);
    	add(a[i]);
    }
    memset(bit,0,sizeof(bit));
    ll ans=0;
    for(int i=n;i>=1;i--){
    	ans+=min(l[i],n-i-query(a[i]));
    	add(a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

这里看题解时学到了一个代码技巧，用BIT左下角计数时是不容易写错的，由于原序列中 a_i\in[1,n] ，那么不难发现 n-a_i+1\in[1,n] ，因此可对每一个 a_i 与映射到 n-a_i+1 ，可将左上角计数转化为左下角计数。因此代码可优化为：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+9;
int n;
int a[maxn],b[maxn];
int bit[maxn],l[maxn]; // l[i]代表i左边有几个比i大的
int lowbit(int x){
    return x&(-x);
}
void add(int i){
    for(;i<=n;i+=lowbit(i)) bit[i]+=1;
}
int query(int i){
    int res=0;
    for(;i>0;i-=lowbit(i)) res+=bit[i];
    return res;
}
ll pref[maxn],suf[maxn];
int main(){
	// freopen("swap.in","r",stdin);
	// freopen("swap.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=n-a[i]+1; // 映射过程，不改变范围，只改变相对大小
    }
    for(int i=1;i<=n;i++){
    	l[i]=query(a[i]-1);
    	add(a[i]);
    }
    memset(bit,0,sizeof(bit));
    ll ans=0;
    for(int i=n;i>=1;i--){
    	ans+=min(l[i],query(a[i]-1));
    	add(a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

PS: 别忘了开long long

xy0v0's Blog

xy0v0's Blog

补题 10.2模拟 T2 序列交换

B. 序列交换

思路分析

代码

分享