题解 | #代理服务器#

//土尔逊Torson 编写于2023/05/31
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

//本函数的目的是在使用代理服务器访问需要访问的服务器时要尽可能的使用与要访问的服务器 IP 不同的代理服务器
//如果要访问的服务器的 IP 中没有和代理服务器的 IP 相同的时，返回 0
//如果有相同的时，需要访问的访问服务器的 IP 与代理服务器 IP 的相同的位置不同
//例如本题在牛客网 题号 KY4 代理服务器 题中示例输入 在访问服务器中下标 1、3、4位置的 IP 与 代理服务器的IP相同
//这种情况下贪心算法使用最远相等的位置来减少代理服务器切换 IP 的次数
//为了保证模拟真实性，我们假设要匹配的访问服务器的 IP 可能存在多次相同的 IP
//所以取最远的位置。每次遍历更新最远位置，直到遍历完全。

int getCSST(vector<string>& proxy, vector<string>& server, int m) {
	// getCSS: get Counting Server Switched Times
	// getCSS: 的意思是获得代理器（代理服务器）切换的次数
	int index = 0, count = 0;
	// index: 表示在每一轮循环 server 遍历时的起始记录下标
	while (index < m) {
		int maxn = 0; 
		// maxn: 表示每次循环中 index 从本轮最初位置需要移动到下轮设置起始位置的最大位移距离
		// 开始遍历代理服务器
		for (string ip : proxy) {
			int j = index;
			while (j < m && ip != server[j]) {
				j++;
			}
			maxn = max(maxn, j - index);
		}
		if (maxn == 0) { //如果 maxn = 0 则表示输入数据有误，即 m = 0 所以返回 -1
			return -1;
		}
		count++;
		//如果要访问的服务器中没有和代理服务器 IP 相同的时 count = 1; index = m 所以跳出循环
		index += maxn;
	}
	return count - 1;
}

int main() {
	int n, m;//n 代表代理服务器的数量，m 代表访问服务器的数量
	while (scanf("%d", &n) != EOF) {
		vector<string> proxy(n);
		for (int i = 0; i < n; ++i) {//获得 n 个代理服务器
			cin >> proxy[i];
		}
		scanf("%d", &m);
		vector<string> server(m);
		for (int i = 0; i < m; ++i) {//获得 m 个访问服务器
			cin >> server[i];
		}
		printf("%d", getCSST(proxy, server, m));//输出代理服务器最少切换次数
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")