题解 | #代理服务器#

简单贪心算法

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    while (cin >> n) {
        vector<string> proxy;
        string s;
        while (n--) {
            cin >> s;
            proxy.push_back(s);
        }
        cin >> m;
        vector<string> ip;
        while (m--) {
            cin >> s;
            ip.push_back(s);
        }
        if (proxy.size() == 1) {    //处理代理服务器只有1个的情况
            int flag = false;
            for (int i = 0; i < ip.size(); i++) {
                if (ip[i] == proxy[0]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                cout << "-1" << endl;
            }
            else {
                cout << "0" << endl;
            }
            continue;
        }
        int begin = 0, cnt = 0, pos = 0;
        int i, j;
        while (begin != ip.size()) {    //每次从所有代理服务器中选择一个可以到达最远的ip的位置
            for (i = 0; i < proxy.size(); i++) {
                for (j = begin; j < ip.size(); j++) {
                    if (proxy[i] == ip[j]) {
                        break;
                    }
                }
                pos = max(pos, j);   //可以到达最远的ip的position
            }
            begin = pos;  //下一次开始的位置从position处开始
            cnt++;    //这个位置处需要切换代理服务器了
        }
        cout << cnt - 1 << endl;
    }
    return 0;
}