ARC 147

A - Max Mod Min ​

Problem Statement ​

就是每一次选择序列的最大值和序列的最小值, 然后把最大值 $\mathrm{m}\mathrm{o}\mathrm{d}$ 最小值的值替换最大值, 如果该值等于 $0$, 那么就把最大值删除.

求需要几次这种操作, 使得给定序列的元素个数为一.

Editorial ​

算法1 ​

暴力模拟 $\mathcal{O}(NX)$, $X$ 是答案

算法2 ​

分析问题的单调性, 因为最大值在经过一次操作之后一定严格小于其自身的 $\frac{1}{2}$, 所以每个元素被选作最大值的次数最多为 $\mathcal{O}(\log maxA)$ 次, 所以答案为 $\mathcal{O}(N\log maxA)$.

所以, 根据单调性, 可以用一个双端队列来实现操作, 先对序列进行排序, 在进行模拟, 该做法复杂度有保证.

总复杂度为 $\mathcal{O}(X+N\log N)$

Code ​

signed main(){
  	fastio();
  	int n;
  	cin>>n;
  	F(i, 0, n) cin>>a[i];
  	sort(a, a + n);
  	deque<int> q;
  	F(i, 0, n) q.push_back(a[i]);
	int ans = 0;
	while(q.size()>1){
		int t = q.front(), e = q.back();
		q.pop_back();
		int tmp = e % t;
		if(tmp != 0) {
			q.push_front(tmp);
		}
		++ ans ;
	}
	cout<<ans<<endl;
	return 0;
}

B - Swap to Sort ​

Problem Statement ​

给定一个排列, 有两种操作:

• 操作 A: 交换 $P_i$ 和 $P_{i+1}$.

• 操作 B: 交换 $P_i$ 和 $P_{i+2}$.

求一个操作序列, 使得

• 操作 A 的个数尽可能少.
• 最后序列为单调递增
• 总操作数不超过${10}^5$ $(2\le N\le 400)$

Editorial ​

考虑构造一种操作策略, 使得其满足要求

最小化操作 A 的的个数 ​

首先, 由于交换间隔为$1$或$2$, 可以想到从奇偶性入手.

定义:

• 如果 $P_i$ 和 $i$ 奇偶性相同, 则称 $i$ 为好下标, 反之则为坏下标, 序列的坏下标总数记作序列的不和谐度.

操作 A 中, 序列的不和谐值变化 $-2,2$ 或 $0$.

操作 B 中, 序列的不和谐值不发生变化.

所以操作 A 至少要被使用 $\frac{1}{2}\times \text{初始不和谐值}$.

使不和谐值为 0 ​

可以发现, 要使操作 A 的个数最少, 必须要在 $i$ 和 $i+1$ 均为坏下标时实施操作, 要达到这点, 需要先使用操作 B 把分散的坏下标聚集起来, 再使用操作 A 进行消除.

排序 ​

由于不和谐值已经为 $0$, 所以只需用操作 B 进行排序即可.

分析总操作数 ​

要使坏下标聚集在一起, 最多要使用 $\frac{N}{2}\times \frac{N}{4}$ 次操作 B

操作 A 最多使用 $\frac{N}{2}$ 次

排序最多使用 $(\frac{N}{2}{)}^2$ 次操作 B

所以当 $N=400$ 时, 操作总和最多是 $60200$, 小于 ${10}^5$.

Code ​

//////////////////// Global Variables ////////////////////

constexpr int N = 500;
int n,m,i,j,a[405];
vector<pair<char,int> > v;

/////////////////////// Functions ////////////////////////

void opt(int x,int l)
{
	swap(a[x],a[x+l]);
	v.push_back(make_pair(l==1?'A':'B',x));
}

////////////////////// Main Execution ////////////////////

signed main(){
  	fastio();
  	cin>>n;
  	Fe(i, 1, n) cin>>a[i];
	Fe(i, 1, n){
		if((i&1)!=(a[i]&1)){
			int j=i+1;
			while((j&1)==(a[j]&1)) j+=2;
			while(j>i+1) opt(j-=2,2);
			opt(i,1);
		}
	}
	Fe(i, 1, n){
		Fe(j, 1, n-2){
			if(a[j]>a[j+2]) opt(j,2);
		}
	}
	cout<<(int)v.size()<<endl;
	fitr(v,it){
		cout<<it->fi<<' '<<it->se<<endl;
	}
	return 0;
}

C - Min Diff Sum ​

Problem Statement ​

$N$ people, numbered $1,2,\dots ,N$, are going to stand on the number line. Let's denote by $x_i$ the coordinate the Person $i$ stands at. Then, $x_i$ should be an integer satisfying $L_i\le x_i\le R_i$. Multiple people can occupy the same coordinate.

We define the dissatisfaction level as the following formula:

Find the minimum possible value of the dissatisfaction level.

Constraints ​

$2\le N\le 3\times {10}^5$

$1\le L_i\le R_i\le {10}^7(1\le i\le N)$