相当有难度的一道题。可以用分阶段的贪心算法做，但需要大致证明局部最优解可以收敛到全局最优。
假设有服务器ABCD，访问序列去除掉无关项、只剩下CBDA...CD
假设A是一步之内可以到达的最远点。由于要从A换成别的服务器，第二步可以到达除A外单步之内最远的字母。
又由于A是从起点出发、第一步可到达的最远点，则其它字母必然在A之前出现至少一次(否则假设不成立)。
假设第一步取的不是A而是其他字母，则必然有：第二步到达的位置<=第一步取A在第二步可到达的位置。

【详细论证】任取非A字母B，也可以换成CD
第一步从起点到B，则第二步从B到最远的非B字母，也就是字母A、或者非A非B的字母X
//注意，我们假设了A是第一步可到达的最远位置，故第一个B在第一个A之前
如果第二步选A，显然刚到达第一个A，肯定要比第一步就选A要近
如果这个字母在第一个B和第一个A之间出现，那么甚至都摸不到第一个A
如果这个字母在第一个B和第一个A之间不出现，那么第二步到达的距离一样远

因此，在本题中使用贪心算法可以从局部最优收敛到全局最优。相当于只是剪了个枝。

【分阶段贪心】自己随便起了个名字，就是每步都选能走最远距离的字母(代理服务器)，直到抵达目标


【需要注意的坑】vector的pop_back是删除最后一个，不是第一个，删第一个要用erase 

#include<iostream>
#include<vector>
#include<map>
#include<string> 
#include<algorithm>
using namespace std;



void Question7_1(){//习题7.1  清华大学  代理服务器 
    int n,m;
    while(cin>>n){
        string ip;
        //初始化代理服务器
        map<string,vector<int>> agent;
        vector<int> empty;
        empty.push_back(5000);//5000表示在访问序列中未出现、可以直接干到底
        for(int i=0;i<n;i++){
            cin>>ip;
            agent[ip] = empty;
        }
        cin>>m;
        //初始化访问列表
        vector<string> visit;
        for(int j=0;j<m;j++){
            cin>>ip;
            visit.push_back(ip);
            //要访问的ip不是代理服务器，可以不用管
            map<string,vector<int>>::iterator finder = agent.find(ip);
            if(finder==agent.end()) continue;
            //访问的ip是代理服务器时，记录在访问列表中出现的位置
            //也就相当于这个代理服务器每次可到达的最远距离
            //注意补正，如果不能直接干到底就把那个5000给去掉
            if(finder->second[0]==5000) finder->second.pop_back();
            finder->second.push_back(j);
        }
        //分阶段贪心策略
        int step = 0;
        string ban;
        int maxPos = 0;
        string maxKey;
        //只有一台服务器且不能直通末尾，无法完成目标 
        if(n==1&&agent.begin()->second[0]<m){
            step = -1;
        }
        while(step!=-1 && maxPos<m){
            //搜寻本轮能到达的最远距离
            map<string,vector<int>>::iterator it = agent.begin();
            while(it!=agent.end()){
                //上一轮要换代理服务器，因此本轮ban掉这个
                if(it->first!=ban && it->second[0]>maxPos){//寻找最远
                    maxKey = it->first;
                    maxPos = it->second[0];
                }
                it++;
            }
            ban = maxKey;
            //到达末尾，跳出
            if(maxPos>=m) break;
            //否则，清除掉已经经过的位置
            it = agent.begin();
            while(it!=agent.end()){
                while(it->second[0]<=maxPos){
                    it->second.erase(it->second.begin());//pop_back是删除最后一个，第一个要用erase
                    if(it->second.size()==0){
                        //不应该erase掉，应该当作可以直达末尾、填充一个5000
                        it->second.push_back(5000);
                        break;
                    }
                }
                it++;
            }
            //所经过的步数+1
            step++;
        }
        
        //最终输出
        cout<<step<<endl;
    }
}

int main(){
	Question7_1();
	 
	return 0;
}