王道机试指南 习题7.1 代理服务器

题目：

算法：

贪心策略，每次寻找访问序列中第一次出现与代理服务器ip相同的位置的最大值处，在该处切换一次代理服务器；然后再从该处出发再次寻找第一次出现与代理服务器ip相同的位置的最大值处，直到走完访问序列。（注意：若代理数量为1，但需要访问它本身，则没有符合要求的安排方式，输出-1）

代码：

#include <iostream>
#include <string>
using namespace std;

void FindPos(int* pos,int n,int m,string* a,string* b,int j0){
    for(int i=0;i<n;i++){//初始化pos为m
        pos[i]=m;
    }

    for(int i=0;i<n;i++)//从j0位置出发，依次寻找访问序列中第一次与各代理服务器ip相同的位置
        for(int j=j0;j<m;j++)
            if(a[i]==b[j] && pos[i]==m) pos[i]=j;
}

int main() {
    int n,m;
    while(cin>>n){
        string a[n];
        for(int i=0;i<n;i++) cin>>a[i];
        cin>>m;
        string b[m];
        for(int i=0;i<m;i++) cin>>b[i];

        if(n==1 && a[0]==b[0]){//若代理数量为1，但需要访问它本身，则没有符合要求的安排方式
            cout<<-1<<endl;
            continue;
        }

        int pos[n];//记录访问序列中第一次出现与代理服务器ip相同的位置
        int step=0;//记录当前走到哪了
        int count=0;//记录切换代理服务器的次数
        while(step<m){//还没走完所有访问序列则继续循环
            FindPos(pos,n,m,a,b,step);////从step位置出发，依次寻找访问序列中第一次与各代理服务器ip相同的位置

            int max=0;//寻找第一次出现与代理服务器ip相同的位置的最大值
            for(int i=0;i<n;i++){
                if(pos[i]>max){
                    max=pos[i];
                }
            }

            if(max==m) break;//若max==m，说明存在一个代理服务器与后续ip访问序列都不相同，跳出循环
            else{//否则在第一次出现与代理服务器ip相同的位置的最大值处继续循环，且切换代理服务器次数加1
                step=max;
                count++;
            }
        }
        cout<<count<<endl;

    }
    return 0;
}

运行结果：

• 测试用例1

• 测试用例2

• 测试用例3