题解 | 代理服务器

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int findMinSwitches(const vector<string>& proxies,const vector<string>& servers);

int main() {
    int a,b;
    scanf("%d",&a);
    vector<string> proxies(a); // 定义代理服务器
    for(int i=0;i<a;i++)cin>>proxies[i];
    scanf("%d",&b);
    vector<string> servers(b); // 定义服务器
    for(int i=0;i<b;i++)cin>>servers[i];
    cout<<findMinSwitches(proxies,servers)<<endl;
}
// 64 位输出请用 printf("%lld")

// 返回最小转换数
int findMinSwitches(const vector<string> &proxies,const vector<string> &servers){
    int n=proxies.size();
    int m=servers.size();
    int current_proxy=-1; // 当前未选择代理
    int switch_count=0; // 切换代理次数

    for(int j=0;j<m;j++){
        if(current_proxy==-1||proxies[current_proxy]==servers[j]){// 第一次选择代理或要切换代理（遇到一样IP）
            if(current_proxy!=-1) switch_count++;
            int best_proxy=-1;
            int best_adaptCount=0;
            for(int i=0;i<n;i++){
                int count=0;
                for(int k=j;k<m;k++){
                    if(servers[k]==proxies[i])break;
                    count++;
                }
                if(count>best_adaptCount){
                    best_proxy=i;
                    best_adaptCount=count;
                }
            }
            current_proxy=best_proxy;
            if(current_proxy==-1) return -1;
        }
    }
    return switch_count;
}