并查集（冰茶鸡x_x）

环

不难发现，可以将数位置和它排序后的位置转化成一个环。假设不形成环，那么最后一定有一个数换不回去，所以这些数肯定是由一些环组成的。

归位（贪心）

考虑一个环，每次交换一定会将一个数（x）归位，y是帮助他归位的数，那代价就是x+y。既然x一定要加，那y肯定越小越好。

答案

将每个环归位所需的代价和，就是最后的答案。

/*
1、环内最小换
2、环外最小换 
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1e4+10;
	const ll M = 1e5+10;
	struct node {
		ll id;
		ll x;
	}a[N];
	ll n, in=M, ans;
	ll f[N], s[N], z[N], cnt[N];
	ll find (ll x) {
		if (f[x]==x) return x;
		return f[x] = find(f[x]);
	}
	bool cmp (node a, node b) {
		return a.x<b.x;
	}
	void work()
	{
//		freopen("a.in", "r", stdin);
		cin>>n;
		for (ll i=1; i<=n; i++) f[i]=i;
		for (ll i=1; i<=n; i++) {
			cin>>a[i].x;
			cnt[i] = 1;
			a[i].id = i;
			s[i] = z[i] = a[i].x; //环和 环最小 
			in = min(in, a[i].x);
		}
		sort(a+1, a+1+n, cmp);
		for (ll i=1; i<=n; i++) {
			if (a[i].id==i) continue;
			ll x = find(i);
			ll y = find(a[i].id);
			if (x!=y) {
				f[y] = x;
				s[x] += s[y];
				cnt[x] += cnt[y];
				z[x] = min(z[x], z[y]);
			}
		}
		for (ll i=1; i<=n; i++) {
			if (f[i]==i) {
				ll t = (cnt[i]-1)*z[i]+s[i]-z[i]; //环内 
				ans += min(t, cnt[i]*in+s[i]+in+z[i]); //环外 
			}
		}
		cout<<ans<<'\n';
	}
} 

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

首先我们发现我们可以对于每个数当前的位置与想要的位置进行连边，然后容易注意到成为了一个环

然后我们可以发现对于这个环，肯定要让最小值尽可能的多用几次，那么我们把最小值当前在什么位置与该位置应该填什么数进行交换然后记录最小值

或者还有另一种可能，也就是把全局最小值与每一个数进行交换，然后求出最小值，首先把全局最小值与该环内的最小值进行交换，然后再与其他的值交换

那么如果是以第 $i$ 个点为起点环内交换，我们可以得到以下式子

$$\min((cnt_i-1)\times minn_i+sum_i-minn_i)$$

如果是全局交换：

$$\min((cnt_i-1)\times minx+sum_i-minn_i+2\times (minn_i+minx) $$

这可以使用并查集或者建图跑dfs实现，时间复杂度 $O(n)$

奶牛排序 题解

难点

1. 需要题意转换
2. 需要分两种情况

分析

由上图可知，交换的过程构成了一个环，且最小值“1”被重复使用了两次（一红一绿），推广后易得： 若干个环中，对于每一个环，用环内最小值与其他节点交换。 计算方式就是：

min_itv[x]*(num_itv[x]-1)+sum_itv[x]-min_itv[x]
//环内的最小值与其他所有节点交换：min_itv[x]*(num_itv[x]-1),再加上其他所有节点的权值和：sum_itv[x]-min_itv[x]

那么到这里解决了第一个难点... 还有一种可能是这个环内的数都比较大，重复使用的环内最小值也不够小，那么就需要：先令环内最小值与全局最小值交换，再按上一种方式计算，最后再把环内最小值和全局最小值换回来。

minn*(num_itv[x]-1)+sum_itv[x]-min_itv[x]+2*(min_itv[x]+minn)
//前后两次换最小值：2*(min_itv[x]+minn)

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,minn,ans,fa[N],min_itv[N],num_itv[N],sum_itv[N];
struct node{
	int x,id;
}a[N];
void init(){
	minn=0x7f7f7f7f;
	memset(min_itv,0x7f7f7f7f,sizeof min_itv);
}
bool cmp(node a,node b){
	return a.x<b.x;
}
int find(int x){
	if(x==fa[x])return x;
	return find(fa[x]);
}
int cnt(int x){
	int t1=min_itv[x]*(num_itv[x]-1)+sum_itv[x]-min_itv[x];
	int t2=minn*(num_itv[x]-1)+sum_itv[x]-min_itv[x]+2*(min_itv[x]+minn);
	return min(t1,t2);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	init();
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i].x,a[i].id=i;
		minn=min(minn,a[i].x);//全局最小值 
	}
	for(int i = 1;i<=n;i++){
		fa[i]=a[i].id;
		num_itv[i]=1;
		sum_itv[i]=a[i].x;
		min_itv[i]=a[i].x;
	}
	sort(a+1,a+1+n,cmp);
	for(int i = 1;i<=n;i++){//并查集合并 
		if(a[i].id==i)continue;
		int x=find(a[i].id),y=find(i);
		if(x==y)continue;
		fa[x]=y;//父亲 
		num_itv[y]+=num_itv[x];//环内个数 
		sum_itv[y]+=sum_itv[x];//环内和 
		min_itv[y]=min(min_itv[y],min_itv[x]);//环内最小值 
	}
	for(int i = 1;i<=n;i++)if(i==fa[i])ans+=cnt(i);
	cout<<ans<<'\n';
	return 0;
}

场切蓝题结束2025，简直完美。

题意

给一个长度为 $n$ 的无重整数序列 $a$，每次可以任选两个元素 $i,j$ 交换，代价为 $a_i+a_j$,求将序列变为升序序列的最小代价。可以 $O(nlogn)orO(值域)$ 做哦。

(赛时zt~姐姐~哥哥写的前一种复杂度，我写的后一种)

思路

考虑每个点都有唯一一个目标位置，显然可以借助一点图论的思维，把每个元素和它的目标位置连线，这样会形成多个环（可以画图推推），容易发现一个长度大于等于 2 的环（非自环）包含的 $pos$ 和 $val_{kth}$ 一一对应。且每个点都不在目标位置。

单独考虑每个环（玩弄了几个小时小纸片）

冗杂的思考过程每个人都不一样，这里给出一种易于理解的思考方式。（艹凡太好用了）

我们前面发现每个点都不在目标位置，所以每个点要至少被交换一次，这个代价是定死了的，也就是代价组成中的 $a_i$ 固定了，这时候我们只能寄希望于最小化 $a_j$，理想化状态是所有 $a_j$ 都是环上的 $a_{min}$，经过画图模拟我们发现，这样一定是可完成的，就是用最小值不断的和其它值交换，总计交换 $n-1$ 次使序列有序，答案为 $a_{min}(n-1)+(sum-a_{min})$ （推推式子很好推的）。

然后就结束了......吗？

不同环之间是可能有相互影响的，n老师给的大样例还只有一个环，可谓居心叵测。具体来说，我们用当前环中的最小值进行交换可能是不优的，当 $a_{min}$ 过大时，可能不如把全局最小值交换进来顶替 $a_{min}$ 的位置，最后再把全局最小值交换回去。（这里还要再推一个式子）

代码

赛时代码能跑就行写的很丑啦不要喷啊

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+17;
int t[N],tot;
bool vis[N];
struct node{
	int val,nxt;
}q[N];int n,ans;
int res,minn=1e9+19;
int b[N];
signed main(){
	//freopen("ex.in","r",stdin);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> q[i].val;
		b[i]=q[i].val;
		minn=min(minn,q[i].val);
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) {
		q[i].nxt=lower_bound(b+1,b+n+1,q[i].val)-b;
	}
	for(int i=1;i<=n;i++){
		if(q[i].nxt==i||vis[i]) continue;
		int mi=q[i].val,now=i;
		vis[i]=1;
		int cnt=1,sum=q[i].val;
		while(vis[q[now].nxt]==0){
			cnt++;
			now=q[now].nxt;
			vis[now]=1;sum+=q[now].val;
			mi=min(mi,q[now].val);
		}
		if(mi==minn){
			ans+=(sum-mi)+(cnt-1)*mi;
		}
		else{
			int tmp=(sum-mi)+(cnt-1)*mi;
			tmp=min(tmp,(minn+mi)*2+(sum-mi)+(cnt-1)*(minn));
			ans+=tmp;
		}
	}cout << ans;
	return 0;
}