它的思想很巧妙
问题
给定一串数字，使得它们之间两两交换，交换的代价为两个数字的和，最后使得这一串数字变得有序。问最小的权重是多少？
题解
我们经过找规律，发现了下面的规律：
数字与位置能构成若干个环，环内的最小的元素，作为交换的媒介，不断的使数组变得有序，代价为：
\(\sum w_{i}+(n-2)·min(w_i)\)， 这里讨论的都是环内的元素
但是不光是每一个环内的元素， 我们还要借助其环内的最小的元素。
例如：(2 1) (8 10 7 9),若按照上面的规则进行相应的变换，最小的权重为51.事实上，我们可以将7和1进行交换，然后1作为媒介进行交换，最后回来，最小的权重为49.公式为：\(\sum w_i+(n-2)·min\_circle+2·(min\_circl+min\_global)-(n-1)·(min\_circle-min\_global)\)后面的在前面的基础之上分别是两圈交换的代价和全局最小元素最为媒介减少的代价
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| #include <bits/stdc++.h> using namespace std; const int maxn = 1e3+10; const int maxv = 1e4+10; int n; int id[maxv]; int weight[maxn]; int temp[maxn]; bool vis[maxn]; int min_value; void solve(){ for(int i=0; i<n; i++){ temp[i] = weight[i]; } sort(temp, temp+n); for(int i=0; i<n; i++) id[temp[i]] = i; int ans = 0; for(int i=0; i<n; i++){ if(vis[i]) continue; int cur = i; int number = 0; int w = 0; int min_weight = 1e9; while(true){ vis[cur] = true; min_weight = min(min_weight, weight[cur]); number++; w+=weight[cur]; cur = id[weight[cur]]; if(vis[cur]) break; } ans += min(w+(number-2)*min_weight, w+(number-2)*min_weight+2*(min_value+min_weight) -(number-1)*(min_weight-min_value)); } printf("%d\n", ans); return ; } int main() { while(~scanf("%d", &n)){ memset(vis, 0, sizeof(vis)); min_value = 1e9; for(int i=0; i<n; i++){ scanf("%d", &weight[i]); min_value = min(min_value, weight[i]); } solve(); } return 0; }
|
题外话
上次去NWU的预热赛有一个交换的问题，就是判断有多少个圈的问题
未解决的问题
