[luogu] P2127 序列排序 思维题

前言

传送门 :

非常好的一个思维题

题意

给定 a [ ] , a [ i ] ∈ ( 0 , 1 e 9 ) a[],a[i]\in(0,1e9) a[],a[i]∈(0,1e9),每次你可以交换数组中的两个数,花费 a [ i ] + a [ j ] a[i]+a[j] a[i]+a[j]

问使得升序排序的最小花费

思路

一开始用树状数组写 , T T T飞了,看到题解中竟然用并查集维护集合Orz

例如 :

3
2 3 1 

显然,2和1交换一次,2再和3交换一次,我们会发现所有的操作构成了一个环

因此刚刚那个操作可以的贡献如下 : ( s z [ i ] − 1 ) ∗ m i n n [ i ] + s u m [ i ] − m i n n [ i ] (sz[i]-1)*minn[i]+sum[i]-minn[i] (sz[i]−1)∗minn[i]+sum[i]−minn[i]

也就是考虑当前这个环所在的集合,使用 最 小 值 最小值 最小值进行交换

当然我们还需要考虑 使用环外的最小值进行交换

( s z [ i ] − 1 ) ∗ m i n a + s u m [ i ] − m i n n [ i ] + 2 ∗ ( m i n a + m i n n [ i ] ) (sz[i]-1)*mina+sum[i]-minn[i]+2*(mina+minn[i]) (sz[i]−1)∗mina+sum[i]−minn[i]+2∗(mina+minn[i])

这样子对于每一个集合都进行这种操作,即可球的最后的答案

写的有点仓促了,不懂的话可以画图理解一下

Code

const int N = 1e5+10;
struct node{
	int id,val;
	bool operatorn;
	for(int i=1;i>a[i].val;
		p[i] = a[i].id =  i;
		min_arry[i] = sum[i] = a[i].val;
		sz[i]=1;
		minn =min(minn,a[i].val);
	}

	sort(a+1,a+1+n);
	for(int i=1;i