思路
其实就是想要尽可能使用和要访问服务器没有交集的代理服务器。
如果要访问的服务器中没有和代理服务器 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); } }