题解 | 代理服务器

寻找最少的切换次数，实际上只要让最晚出现的服务器与代理服务器重合时对应的IP地址作为此前所有服务器的代理即可。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

int main() {
    int n, m;
    std::vector<std::string> agentIP;
    std::vector<std::string> serverIP;
    int ans = -1;
    std::string IP;
    while (std::cin >> n) {
        for (int i = 0; i < n; i++) {
            std::cin >> IP;
            agentIP.push_back(IP);
        }
        std::cin >> m;
        for (int i = 0; i < m; i++) {
            std::cin >> IP;
            serverIP.push_back(IP);
        }
        ans = 0;
        std::vector<bool> markedAgent(n);
        for (int i = 0; i < n; i++) {
            markedAgent[i] = false;
        }
        for (int i = 0; i < m; i++) {
            if (ans == -1) break;
            for (int j = 0; j < n; j++) {
                if (serverIP[i] == agentIP[j]) {
                    // 访问的服务器就是代理服务器
                    if (n == 1) {
                        // 备选代理服务器没有其他选项，对应无法规划出合适的方案
                        ans = -1;
                        break;
                    }

                    /* Greedy
                    依次访问服务器IP，如遇到代理服务器则标记。
                    直到遇到一个代理服务器并标记后所有的代理服务器均已被标记，
                    那么这时可以理解为此前所有服务器（不含当前）访问均为这个代理服务器。
                    此时切换代理，并清除这个代理服务器之外的所有标记，如此反复。
                    */

                    markedAgent[j] = true; // 标记代理服务器
                    bool allAgentMarked = true;
                    // 判断是否所有代理服务器均被标记过
                    for (int k = 0; k < n; k++) {
                        if (markedAgent[k] == false) {
                            allAgentMarked = false;
                            break;
                        }
                    }
                    if (!allAgentMarked) break;
                    // 此时如果还在循环内则一定是代理服务器均已被标记，对应此前所有的访问全都由代理服务器“j”进行
                    ans++; // 切换
                    for (int k = 0; k < n; k++) {
                        markedAgent[k] = false; // 重置标记
                    }
                    markedAgent[j] = true; // 将切换前的代理服务器标记
                    break;
                }
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}