如何将N个物体均匀的放入N个相邻移动的地方

原文:https://www . geeksforgeeks . org/如何通过相邻移动将 n 个对象平均放置到 n 个位置/

假设有 N 个对象不均匀地分布在 N 个容器中。您可以将一个对象从一个容器移动到相邻的容器，这被认为是一次移动。什么策略可以最大限度地减少移动次数，从而保持时间复杂度为 0(N)？
示例:

例 1。假设您有 5 个容器，填充为:
1，2，1，1，0
您将需要三次移动来将一个对象从第二个容器传递到最后一个- >，从第二个移动到第三个，然后移动到第四个，最后移动到第五个:
1，1，2，1，0
1，1，1，2，0
1，1，1，1
示例 2。现在更复杂一点。
假设你有 5 个容器，所有对象都在最后一个容器中:
0，0，0，0，5
显然，你会从右向左移动:
0，0，0，1，4
0，0，1，0，4
0，1，0，0，4
1，0，0，0，4
1，0，0，1，3
1，0，1，0，3
所有物体都在中间:
0，0，5，0，0
看起来没错:
0，1，4，0，0
1，0，4，0，0
1，1，3，0，0
1，1，2，1，0
1，1，2，0，1
1，1，1，1，1
需要 6 次移动

这个问题弱弱地提醒了一个所谓的鸽巢或狄利克雷原理–n 个物品放入 m 个容器中，用 n > m，那么至少一个容器必须包含一个以上的物品。因此它出现在标题中。
进场听起来相当琐碎:沿着集装箱排从头到尾移动，如果你遇到一个空集装箱，把它装满，如果你遇到一个有几个物体(不止一个)的集装箱，尽量把量减少到只有一个。
更准确地说，一个人必须保持一个有太多对象的容器队列和另一个空位置队列，并使用它们来传递对象。显然，由于我们试图一有可能就传递对象，所以在我们做了所有可能的运动后，每一步都会有一个队列变空。
再详细一点:
每次遇到空的地方，我们都会检查有多个物体的容器队列中是否有东西，如果有，就拿一个物体把空的地方填满。如果没有，将这个空位置添加到队列中。
每次遇到人满为患的集装箱，都要检查空位的队列是否有东西，如果有，尽量把当前集装箱的物品尽可能多的放入这些空集装箱，从它们的队列中取出。如果没有空的，将过度拥挤的集装箱推到满集装箱的队列中。
过度拥挤集装箱的队列中有成对的数字:多余物品的位置和数量。空容器的队列只保留位置的数字，因为它们是空的。
如果输入是以对象 A 的坐标数组的形式提供的，首先将其重组为每个位置的数量数组。
这个问题可以不止一个维度，就像启发了这篇文章的编码挑战 Selenium 2016 一样。但是因为维度是独立的，所以每个维度的结果只是被总结以得到最终的答案。
余数问题的完整实现包括最终答案取模 10^9+7.
示例:

Input :
Coordinates of objects are
X = [1, 2, 2, 3, 4] and array Y = [1, 1, 4, 5, 4]
Output :
5
Input :
X = [1, 1, 1, 1] and array Y = [1, 2, 3, 4]
Output :
6
Input :
X = [1, 1, 2] and array Y = [1, 2, 1]
Output :
4


注:还有另一种方法，可能会在另一篇文章中介绍，灵感来自于《余度未来移动性挑战》中一个更难的问题。包括以下步骤:

• 从每个位置减去 1，现在我们争夺所有 0，而不是所有 1


• 将数组切割成片段，例如在每个片段中，对象的移动都是在一个方向上，每个片段的开头和结尾都可以去掉零。样品:1，0，-1，0，-2，2 切成 1，0，-1 和-2，2。切割点由前缀和的零发现


• 计算每个碎片的第二个积分。那是前缀从左到右的前缀。最正确的值是移动量。样本序列:1，0，-1。前缀是 1，1，0。第二个前缀是 1，2，2。这个片段的答案是 2(从 0 到 2 的两次移动)


• 结果是所有片段结果的总和

最后执行第一种方式:

卡片打印处理机（Card Print Processor 的缩写）

#include
#include
using namespace std;
#define MODULO 1000000007
/* Utility function for one dimension
unsigned long long solution(vector& A)
Parameters: vector& A - an array of numbers
of objects per container
Return value: How many moves to make all containers
              have one object */
unsigned long long solution(vector& A)
{
    // the final result cannot be less than
    // zero, so we initiate it as 0
    unsigned long long res = 0;
    // just to keep the amount of objects for future usage
    const unsigned int len = (unsigned int)A.size();
     // The queue of objects that are ready for move,
     // as explained in the introduction. The queue is
     // of pairs, where the first value is the index
     // in the row of containers, the second is the
     // number of objects there currently.
    queue > depot;
     // The queue of vacant containers that are ready
     // to be filled, as explained in the introduction,
     // just the index on the row, since they are
    // empty - no amount, zero is meant.
    queue depotOfEmpties;
    // how many objects have coordinate i
    vector places(len, 0);
    // initiates the data into a more convenient way,
    // not coordinates of objects but how many objects
    // are per place
    for (unsigned int i = 0; i         places.at(A.at(i) - 1)++;
    }
    // main loop, movement along containers as
    // explained in the introduction
    for (unsigned int i = 0; i         // if we meet the empty container at place i
        if (0 == places.at(i)) {
            // we check that not objects awaiting
            // to movement, the queue of objects
            // is possible empty
            if (depot.empty()) {
                 // if true, no object to move, we
                 // insert the empty container into
                 // a queue of empties 
                depotOfEmpties.push(i);
            }
            // there are some object to move, take
            // the first from the queue  
            else {
                // and find how distant it is
                unsigned int distance = (i - depot.front().first);
                // we move one object and making
                // "distance" moves by it
                res += distance;
                // since the result is expected MODULO
                res = res % MODULO;
                // now one object left the queue
                // for movement, so we discount it
                depot.front().second--;
                 // if some elements in the objects
                 // queue may loose all objects, 
                while (!depot.empty() && depot.front().second <1) {
                    depot.pop(); // remove all them from the queue
                }
            }
        }
        // places.at(i) > 0, so we found the current
        // container not empty
        else {
            // if it has only one object, nothing must
            // be done
            if (1 == places.at(i)) {
                // so the object remains in its place,
                // go further
                continue;            
            }
            // there are more than one there, need
            // to remove some
            else {
                // how many to remove? To leave one
                unsigned int pieces = places.at(i) - 1;
                // how many empty places are awaiting to fill
                // currently? Are they enough to remove "pieces"?
                unsigned int lenEmptySequence = depotOfEmpties.size();
                // Yes, we have places for all objects
                // to remove from te current 
                if (pieces <= lenEmptySequence) {
                    // move all objects except one
                    for (unsigned int j = 0; j                         // add to the answer and apply MODULOto
                        // prevent overflow
                        res = (res + i - depotOfEmpties.front()) % MODULO;
                        // remove former empty from the queue of empties
                        depotOfEmpties.pop();
                    }
                }
                // empty vacancies are not enough or absent at all
                else {
                    for (unsigned int j = 0; j                         // fill what we can
                        res = (res + i - depotOfEmpties.front()) % MODULO;
                        // and remove filled from the vacancies queue 
                        depotOfEmpties.pop();
                    }
                    // since we still have too many objects in
                    // this container, push it into the queue for
                    // overcrowded containers
                    depot.push(pair(i,
                                        pieces - lenEmptySequence));
                }
            }
        }
    }
    // the main loop end
    return res; // return the result
}
/* Main function for two dimensions as in
   Codility problem
int solution(vector& A, vector& B)
Parameters:
 vector& A - coordinates x of the objects
 vector& B - coordinates y of the objects
Return value:
 No. of moves to make all verticals and horizontals
 have one object
*/
int solution(vector& A, vector& B)
{
    unsigned long long res = solution(B);
    res += solution(A);
    res = res % MODULO;
    return (int)res;
}
// test utility for the driver below
#include
void test(vector& A, vector& B, int expected,
         bool printAll = false, bool dOnotPrint= true)
{
    int res = solution(A, B);
    if ((expected != res && !doNotPrint) || printAll) {
        for (size_t i = 0; i             cout <        }
        cout <        for (size_t i = 0; i             cout <        }
        cout <        if (expected != res)
            cout <<"Error! Expected: " <        else
            cout <<"Expected: " <    }
    cout <<" Result: " <}
// Driver (main)
int main()
{
    int A4[] = { 1, 2, 2, 3, 4 };
    int B4[] = { 1, 1, 4, 5, 4 };
    vector VA(A4, A4 + 5);
    vector VB(B4, B4 + 5);
    test(VA, VB, 5);
    int A0[] = { 1, 1, 1, 1 };
    int B0[] = { 1, 2, 3, 4 };
    VA = vector(A0, A0 + 4);
    VB = vector(B0, B0 + 4);
    test(VA, VB, 6);
    int A2[] = { 1, 1, 2 };
    int B2[] = { 1, 2, 1 };
    VA = vector(A2, A2 + 3);
    VB = vector(B2, B2 + 3);
    test(VA, VB, 4);
    // square case
    int A3[] = { 1, 2, 3, 1, 2, 3, 1, 2, 3 };
    int B3[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3 };
    VA = vector(A3, A3 + 9);
    VB = vector(B3, B3 + 9);
    test(VA, VB, 54);
    // also
    int A5[] = { 7, 8, 9, 7, 8, 9, 7, 8, 9 };
    int B5[] = { 7, 7, 7, 8, 8, 8, 9, 9, 9 };
    VA = vector(A5, A5 + 9);
    VB = vector(B5, B5 + 9);
    test(VA, VB, 54);
    int A6[] = { 1, 1, 2, 3 };
    int B6[] = { 1, 2, 3, 4 };
    VA = vector(A6, A6 + 4);
    VB = vector(B6, B6 + 4);
    test(VA, VB, 3);
    test(VB, VA, 3);
    int A7[] = { 1, 1, 3, 5, 5 };
    int B7[] = { 1, 5, 3, 1, 5 };
    VA = vector(A7, A7 + 5);
    VB = vector(B7, B7 + 5);
    test(VA, VB, 4);
    test(VB, VA, 4);
    // smaller square case
    int A8[] = { 1, 2, 1, 2 };
    int B8[] = { 1, 1, 2, 2 };
    VA = vector(A8, A8 + 4);
    VB = vector(B8, B8 + 4);
    test(VA, VB, 8);
    int A9[] = { 3, 4, 3, 4 };
    int B9[] = { 3, 3, 4, 4 };
    VA = vector(A9, A9 + 4);
    VB = vector(B9, B9 + 4);
    test(VA, VB, 8);
    int A10[] = { 1, 2, 3, 4, 1, 2, 3, 4, 1,
                     2, 3, 4, 1, 2, 3, 4 };
    int B10[] = { 1, 1, 1, 1, 2, 2, 2, 2, 3,
                      3, 3, 3, 4, 4, 4, 4 };
    VA = vector(A10, A10 + 16);
    VB = vector(B10, B10 + 16);
    test(VA, VB, 192);
    int A11[] = { 13, 14, 15, 16, 13, 14, 15,
         16, 13, 14, 15, 16, 13, 14, 15, 16 };
    int B11[] = { 13, 13, 13, 13, 14, 14, 14,
         14, 15, 15, 15, 15, 16, 16, 16, 16 };
    VA = vector(A11, A11 + 16);
    VB = vector(B11, B11 + 16);
    test(VA, VB, 192);
    return 0;
}


Output: 

Result: 5
Result: 6
Result: 4
Result: 54
Result: 54
Result: 3
Result: 3
Result: 4
Result: 4
Result: 8
Result: 8
Result: 192
Result: 192