题解 | #代理服务器#

#include <iostream>
using namespace std;

int main()
{
    int m;//代理服务器个数
    int n;//服务器个数
    while(cin>>m)
    {
        string d[m];
        int lu[m];
        for(int i=0; i<m; i++)
            cin>>d[i];
        cin>>n;
        string f[n];
        for(int i=0; i<n; i++)
            cin>>f[i];
        int fang=0;//标识现在访问到哪个服务器
        bool guo[m];
        int Count=-1;
        while(fang!=n)
        {
            //每次初始化
            for(int j=0; j<m; j++)
            {
                guo[j]=false;
                lu[j]=0;
            }
            //确定每个代理服务器能走多长的路
            for(int i=fang; i<n; i++)
            {
                for(int j=0; j<m; j++)
                {
                    if(!guo[j]&&d[j]!=f[i])
                        lu[j]++;
                    else if(!guo[j]&&d[j]==f[i])
                        guo[j]=true;
                }
            }
            //选择
            int Max=0;
            for(int i=0; i<m; i++)
            {
                if(Max<lu[i])
                    Max=lu[i];
            }
            if(Max==0)
            {
                Count=-1;
                break;
            }
            fang=Max+fang;
            Count++;
        }
        cout<<Count<<endl;
    }
    return 0;
}

思路：每次选择能访问服务器个数最多的代理服务器，此为贪心。

对于没有符合要求的安排方式的理解：即没有选择，何为没有选择？就是没有与下一个服务器不相等的代理服务器，什么时候会出现？只有一个代理的时候，遇到与其IP相等的服务器，则别无选择。在代码上体现为能访问服务器个数最多为0，此时即可退出循环，输出-1。