机器人和容器最小化问题，需要的方法

Question

鉴于此 problem:

You have a warehouse with M containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be 1 meter apart. You also have 2 robots that can pick up 1 piece of candy and transport it between any two containers.

The robots take instructions in the form of queries consisting of two integers, Ma and Mb, respectively. To execute a query, a robot travels to container Ma, picks up 1 candy, transports it to container Mb, and then stops at Mb until it receives another query.

Calculate the minimum total distance the robots must travel to execute N queries in order.

Note: You choose which robot executes each query.

最初我假设我应该简单地选择更接近的机器人来执行移动，但是这种方法在某些测试用例中失败了，谁能解释为什么这种方法对所有情况都无效，什么是正确的方法，谢谢。

示例输入和预期输出 here。

Answer 1

问题属于动态规划范畴，你自己给问题贴了标签greedy（你的做法确实很贪心）。在某些情况下，给定查询的最小距离（局部最小值）对于完整的查询集（全局最小值）不是最优的。因此，您需要考虑机器人对查询的所有可能分配，但使用 DP 技术，这不是详尽的搜索。

我不想为您详细说明确切的解决方案，因为 DP 上有大量在线资源（制作二维 table 成本，跨列移动 = 机器人 1，跨rows = robot 2，通过table, …找到最优路径。但我想向您展示贪婪方法次优的示例情况。

A机器人1
B机器人2
F查询起点
T查询结束点

用贪心法解决：

 (A)                  B
1 . . F . T . . . . . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
         (A)          B
2 . . . . . . F . T . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
                 (A)  B
3 F T . . . . . . . . . // A is closer to F, travels 8 (to F) + 1 (to T) = 9
    A                 B

总行驶距离：4 + 4 + 9 = 17。

一个最优的方法（可能有多个）：

 (A)                  B
1 . . F . T . . . . . . // A takes query, travels 2 (to F) + 2 (to T) = 4
          A          (B)
2 . . . . . . F . T . . // B takes query, travels 4 (to F) + 2 (to T) = 6
         (A)      B
3 F T . . . . . . . . . // A takes query, travels 4 (to F) + 1 (to T) = 5
    A             B

总行驶距离：4 + 6 + 5 = 15。

请注意，B 接受了第二个查询，即使它不是最接近起点的。

Answer 2

在 C++ 中使用动态编程（如 Aurel Bílý 所解释的）的工作代码：

#include <bits/stdc++.h>
using namespace std;
vector <pair <int,int > > input;
int dp[1002][1002];
int m,n;
int dis(int a,int b)
{
    if(a == 0) return abs(input[b-1].first-input[b-1].second);
    return abs(input[a-1].second-input[b-1].first)+abs(input[b-1].first-input[b-1].second);
}
int func(int i,int j)
{
    if(i+1 == n+1 || j+1 == n+1)
    {
        return 0;
    }
    //cout<<i<<" "<<j<<endl;
    if(dp[i][j] != -1)
     return dp[i][j];
    int result = INT_MAX;
    result = min(func(i,j+1)+dis(j,j+1),func(j,j+1)+dis(i,j+1));
    return dp[i][j] = result; 
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>m>>n;
        input.clear();
        input.resize(n);
        for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            input[i] = make_pair(a,b);
        }
        memset(dp,-1,sizeof(dp));
        int first = abs(input[0].first-input[0].second);
       // int second = abs(input[1].first-input[1].second);
        int val = func(0,1)+first;
        cout<<val<<endl;
    }
    return 0;
}

机器人和容器最小化问题，需要的方法

Robots and containers minimization problem, approach needed

algorithm

dynamic-programming

greedy