在最后执行最佳循环排序知道顺序。

Question

我们有列表A，在排序后，需要看起来像列表B，我们有每个数字的努力或“权重”，所以当我们按顺序交换时，它们也是相连的。

知道列表最后应该是什么样子，找出对列表A排序以看起来像lis B所需的最低工作量

我已经为我的问题找到了睡衣，但它在c++代码中位于底部

6 <--- how many numbers there is
w = [2400, 2000, 1200, 2400, 1600, 4000] <----- effort 
a = [1, 4, 5, 3, 6, 2] <----- starting list
b = [5, 3, 2, 4, 6, 1] <----- how it should be sorted

所以当我们移动的时候

2和5我们取第二和第五重并将它们加在一起，所以的工作量是3600，如下所示

a = [1, 4, 2, 3, 6, 5]

sum_effort = 3600

然后我们移动3和4，这一移动再次是3600，如下所示

a = [1, 3, 2, 4, 6, 5]

sum_effort = 7200

然后用5的1，所以这个移动的的努力是4000，一个列表看起来像b列表

sum_effort是11200

我在c++上做了什么

weight = [2400, 2000, 1200, 2400, 1600, 4000]
og = [1, 4, 5, 3, 6, 2]
position = [5, 3, 2,4, 6, 1]

result = 0
for x in range(len(og)):
    suma    = 0
    min_cycle = 0
    len_cycle = 0
    current  = x

    while(1):
    
        min_cycle = min(min_cycle, weight[current])
        
        suma = suma + weight[current]
        current = position[current]
            
        len_cycle += 1
        if current == x:
            break
        
    result += min(suma+(len_cycle-2)*min_cycle, suma+min_cycle+(len_cycle+1)*min_weight)
print(result)

#include <cstdio>
#include <algorithm>

#define REP(a,n) for (int a=0; a<(n); ++a)

using namespace std;

#define INF 1000000000

typedef long long LL;

///////////////////////////

#define MAXN 1000000

int wagi[MAXN];
int orig[MAXN]; // orgin
int perm[MAXN]; // end_pos
bool vis[MAXN]; 

int minw = INF; // minimalna waga

int main()
{
    int N;
    scanf("%d", &N);
    REP(a, N)
    {
        scanf("%d", &wagi[a]);
        minw = min(minw, wagi[a]);
    }
    REP(a, N)
    {
        scanf("%d", &orig[a]);
        --orig[a];
    }
    REP(a, N)
    {
        int nr;
        scanf("%d", &nr);
        --nr;
        perm[nr] = orig[a];
    }
    LL wynik = 0;
    REP(pocz, N)
        if (!vis[pocz])
        {
            int minc = INF; 
            LL suma = 0; 
            int cur = pocz;
            int dl = 0; 
            for (;;) 
            {
                minc = min(minc, wagi[cur]);
                suma += wagi[cur];
                cur = perm[cur];
                vis[cur] = true;
                ++dl;
                if (cur==pocz)
                    break;
            }
            wynik += min(suma+(dl-2)*(LL)minc, suma+minc+(dl+1)*(LL)minw);
        }
    printf("%Ld\n", wynik);
}

我对蟒蛇有点陌生，但如果我不搞清楚，我就不会睡觉了

Answer 1

我决定坐下来试着解决这个问题。如果我理解正确的话，我们将在列表上执行交换，以便将它们按照目标列表中的顺序排序。

我们可以做两种类型的操作。将两个数字交换到目的地，这意味着交换两个数字，它们都在属于自己的地方。并将一个号码交换到目的地，这使得其中一个号码位于它所属的地方，而另一个号码则放在不正确的位置。

完美的交换应该总是优先于一个元素到目的地。在把它写在纸上之后，我还得出结论，当做一个元素去除法互换时，为了最小化和，你移动最小的元素越多，和就越小。

所以，我想出的算法是:在目标中找到最小的权重元素，找出它的位置，切换它们。然后从目标列表和原点列表中删除位于其正确位置上的所有元素(为了找到新的最小权重，如果上一个元素已经在目的地)，循环直到列表为空。

程序将使用一个到目的地互换，以移动最低的重量，只要它可以，当它完成，选择下一个最小的元素。当程序选择其中一个元素作为最小权重时，双向完美互换将解决自己的问题。

我不确定这个算法是否完全正确，尤其是在拐角处的情况下，但这是我所能想出的最好的方法，而且我只有很少的时间。

def remove_correct_places(org,trg,orgw):
    indexes_to_delete = []

    for index, tpl in enumerate(zip(org, trg)):
        if tpl[0] == tpl[1]:
            indexes_to_delete.append(index)

    for index in reversed(indexes_to_delete):
        org.pop(index)
        trg.pop(index)
        orgw.pop(index)

weight = [2400, 2000, 1200, 2400, 1600, 4000]
origin = [1, 4, 5, 3, 6, 2]
target = [5, 3, 2, 4, 6, 1]


weights = {nr+1:item for nr, item in enumerate(weight)}
# list of weights in order corresponding to origin
origin_weights= [weights[x] for x in origin]
sum_ = 0

#ignoring elements that are in their places already
remove_correct_places(origin,target,origin_weights)

# as long as origin isn't empty
while origin_weights:
    # find smallest weight
    min_weight = min(origin_weights)
    # find its index
    min_weight_index = origin_weights.index(min_weight)
    # find which element it corresponds to
    min_weight_element = origin[min_weight_index]

    # find what value should be in that index
    other_element = target[min_weight_index]
    # find index of this value in origin
    other_index = origin.index(other_element)
    # find its weight
    other_weight = weights[other_element]

    # swap the two (both on origin_weight and origin lists) and increase the cumulative sum
    origin[min_weight_index] = other_element
    origin_weights[min_weight_index] = other_weight

    origin[other_index] = min_weight_element
    origin_weights[other_index] = min_weight

    sum_ += other_weight + min_weight

    # removing elements that are on the correct place from the list,
    # because we don't need them anymore
    remove_correct_places(origin, target, origin_weights)

print(sum_)