[cf] Educational Codeforces Round 126 (Rated for Div. 2)

前言

传送门 :

这场好难的样子,难指的是(会写,但是写不出来

A. Array Balancing

给定两个数组,完成多次操作操作后使得

∑ i = 1 n − 1 ( ∣ a i − a i + 1 ∣ + ∣ b i − b i + 1 ∣ ) \sum_{i=1}^{n-1}(|a_i-a_{i+1}|+|b_i-b_{i+ 1}|) ∑i=1n−1​(∣ai​−ai+1​∣+∣bi​−bi+1​∣) 最小

操作描述 :

• 选择一个下标 i i i
• 交换 a i a_i ai​ 和 b i b_i bi​

看着像 d p dp dp,对于每个位置有交换和不交换两种选择

其实我们只需要模拟的时候 直接取 m i n min min即可

a b s ( a [ i ] − b [ i − 1 ] ) + a b s ( b [ i ] − a [ i − 1 ] ) ) abs(a[i]-b[i-1])+abs(b[i] - a[i-1])) abs(a[i]−b[i−1])+abs(b[i]−a[i−1]))表示前面的数进行了交换

Mycode

void solve(){
	cin>>n;

	for(int i=1;i>a[i];
	for(int i=1;i>b[i];
	ll sum = 0;
	for(int i=2;ix;
    	cout1;
		if(check(mid,maxn)||check(mid,maxn+1)||check(mid,maxn+2)){
			ans = mid;
			r = mid-1;
		}else l = mid+1;
	}
	cout