代理服务器

思路

其实就是想要尽可能使用和要访问服务器没有交集的代理服务器。

如果要访问的服务器中没有和代理服务器 IP 相同的，返回 0

如果有相同的，那么每个代理服务器都在某一个位置相同，比如例子中的分别在 1、4、2 处相同，那么贪心策略取最远相同的，然后对剩下的再次进行判断即可。

因为服务器 IP 没有说明是否不重复，所以一个代理服务器 IP 可能在多个位置与要访问的服务器 IP 相同，所以取最远的位置其实是第一次相同时的最远位置。然后更新遍历 sever 的起始地址，直到遍历完全。

#include<iostream>
#include<vector>

using namespace std;

int getCnt(vector<string>& proxy, vector<string>& server, int m){
    // index表示每次遍历 serve 时的起始下标
    int index = 0, count = 0;
    while(index < m){
        int maxn = 0;//代表 index 右移的最大距离
        // 遍历代理服务器
        for(string ip : proxy){
            int j = index;
            while(j < m && ip != server[j]) j ++;
            maxn = max(maxn, j - index);
        }
        if(maxn == 0) return -1;
        count ++;
        index += maxn;
    }
    return count - 1;
}

int main(){
    int n, m;
    while(cin >> n){
        vector<string> proxy(n);
        unordered_map<string, int> mp;
        for(int i = 0; i < n; i ++){
            cin >> proxy[i];
            mp[proxy[i]] = 1;
        }
        cin >> m;
        vector<string> server(m);
        for(int i = 0; i < m; i ++)
            cin >> server[i];
        cout << getCnt(proxy, server, m);
    }
}