单街城市性别约束群体运输：非DP算法错误排查与方案求助

在圣菲耶罗市，所有建筑沿单条街道分布。您作为唯一的出租车司机卡尔，需将n名男孩和m名女孩从街道起点的俱乐部送往更远的家中。出租车最多载客4人，按最远下车点距离计费，每公里1CU，且每辆出租车必须至少包含1名男孩。

输入格式 #

• 第一行输入n（1≤n≤2011）为男孩数量，后续n行每行输入男孩姓名及距俱乐部的距离；
• 接着输入m，后续m行每行输入女孩姓名及距俱乐部的距离；
• 姓名首字母大写，长度1-15字符；距离为非负整数，不超过10000。

任务目标：将人群分配到出租车中，最小化总运输成本。

我的问题 #

该任务需用动态规划（DP）解决，但我尝试用非DP方法实现后，在某测试用例上出错。恳请指出我的算法错误、提供未通过的测试用例，或给出DP解决方案。

我的算法步骤 #

• 排序：将所有人按距俱乐部的距离降序排列，以便按距离顺序下车，最小化总行驶距离；
• 出租车分配：遍历排序后的列表，每辆出租车最多载4人，用标记跟踪是否包含至少1名男孩；
• 确保每车含男孩：若当前出租车无男孩，先从未分配乘客中找男孩替换；若无剩余男孩，则从已分配的前序出租车中调换男孩；
• 成本计算：每辆出租车的成本为乘客中的最大距离。

代码 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct Person {
    string name;
    int distance;
    bool isBoy;
};

// Comparator to sort persons by distance in descending order
bool compareByDistance(const Person &a, const Person &b) {
    return a.distance > b.distance;
}

// Helper function to find the index of the girl with the minimum distance in the taxi
int findMinDistanceGirlIndex(const vector<Person> &taxi) {
    int minDistance = 1e9, minIndex = -1;
    for (int i = 0; i < taxi.size(); ++i) {
        if (!taxi[i].isBoy && taxi[i].distance < minDistance) {
            minDistance = taxi[i].distance;
            minIndex = i;
        }
    }
    return minIndex;
}

// Helper function to find the index of the girl with the maximum distance in the taxi
int findMaxDistanceGirlIndex(const vector<Person> &taxi) {
    int maxDistance = -1e9, maxIndex = -1;
    for (int i = 0; i < taxi.size(); ++i) {
        if (!taxi[i].isBoy && taxi[i].distance > maxDistance) {
            maxDistance = taxi[i].distance;
            maxIndex = i;
        }
    }
    return maxIndex;
}

// Helper function to find the index of the boy with the minimum distance in a taxi
int findMinDistanceBoyIndex(const vector<Person> &taxi) {
    int minDistance = 1e9, minIndex = -1;
    for (int i = 0; i < taxi.size(); ++i) {
        if (taxi[i].isBoy && taxi[i].distance < minDistance) {
            minDistance = taxi[i].distance;
            minIndex = i;
        }
    }
    return minIndex;
}

// Recursive function to pull a boy from previous taxis if necessary
void ensureBoyInPreviousTaxis(vector<vector<Person>> &taxis, vector<Person> &currentTaxi, int taxiIndex) {
    if (taxiIndex < 0) return;  // Base case: no more taxis to go back to
    
    vector<Person> &previousTaxi = taxis[taxiIndex];
    int minBoyIndex = findMinDistanceBoyIndex(previousTaxi);
    int maxGirlIndex = findMaxDistanceGirlIndex(currentTaxi);

    // Swap the girl out with the boy from the previous taxi
    swap(currentTaxi[maxGirlIndex], previousTaxi[minBoyIndex]);

    // Check if the previous taxi still has a boy after the swap
    if (findMinDistanceBoyIndex(previousTaxi) == -1) {
        ensureBoyInPreviousTaxis(taxis, currentTaxi, taxiIndex - 1);
    }
}

// Function to display the contents of all taxis
void displayTaxis(const vector<vector<Person>> &taxis) {
    for (int i = 0; i < taxis.size(); ++i) {
        cout << "Taxi " << i + 1 << ":";
        for (size_t j = 0; j < taxis[i].size(); ++j) {
            cout << (j > 0 ? (j == taxis[i].size() - 1 ? " and " : ", ") : " ") << taxis[i][j].name;
        }
        cout << "." << endl;
    }
}
int main() {
    int n, m;

    // Reading number of boys
    cin >> n;
    vector<Person> people;

    // Reading boys' information
    for (int i = 0; i < n; i++) {
        Person boy;
        cin >> boy.name >> boy.distance;
        boy.isBoy = true;
        people.push_back(boy);
    }

    // Reading number of girls
    cin >> m;

    // Reading girls' information
    for (int i = 0; i < m; i++) {
        Person girl;
        cin >> girl.name >> girl.distance;
        girl.isBoy = false;
        people.push_back(girl);
    }

    // Sort all people by distance in descending order
    sort(people.begin(), people.end(), compareByDistance);

    vector<vector<Person>> taxis; // List of all taxis

    int i = 0;

    // Process until all people are taken home
    while (i < people.size()) {
        vector<Person> taxi;
        bool hasBoy = false;

        // Add first 4 people from the sorted list to the taxi
        for (int j = 0; j < 4 && i < people.size(); ++j) {
            taxi.push_back(people[i]);
            if (people[i].isBoy) {
                hasBoy = true;
            }
            ++i;
        }

        // If there is no boy in the current taxi, try to find one
        if (!hasBoy) {
            bool boyFound = false;

            // Look for a boy in the unallocated list first
            for (int k = i; k < people.size(); ++k) {
                if (people[k].isBoy) {
                    int minGirlIndex = findMinDistanceGirlIndex(taxi);
                    people.insert(people.begin(), taxi[minGirlIndex]);  // Add the girl back to the beginning of the list
                    taxi[minGirlIndex] = people[k];                      // Replace her with the boy
                    people.erase(people.begin() + k);                   // Remove the boy from the list
                    boyFound = true;
                    break;
                }
            }
            // If no boys left in the unallocated list, pull one from previous taxis
            if (!boyFound) {
                ensureBoyInPreviousTaxis(taxis, taxi, taxis.size() - 1);
            }
        }

        // Add this taxi to the list of taxis
        taxis.push_back(taxi);
    }

    // Calculate total cost at the end based on the maximum distance for each taxi
    int totalCost = 0;
    for (const auto &taxi : taxis) {
        int maxDistance = -1; // Initialize to a very small value
        for (const auto &person : taxi) {
            maxDistance = max(maxDistance, person.distance);
        }
        totalCost += maxDistance;
    }

    // Output the total cost and number of trips
    cout << totalCost << endl;
    cout << taxis.size() << endl;

    // Display the contents of all taxis
    displayTaxis(taxis);

    return 0;
}

测试用例 #

输入：

2
Mark 5
Alex 10
5
Anna 1
Maria 12
Carol 10
Elena 8
Lisa 6

输出：

18
2
Taxi 1: Mark, Lisa and Anna.
Taxi 2: Alex, Maria, Carol and Elena.

内容的提问来源于stack exchange，提问作者Andrew S.