题目描述
使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器，并要求不能用代理服务器去访问和它 IP地址相同的服务器（不然客户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方案，使得代理服务器切换的次数尽可能得少。
输入描述
每个测试数据包括 n + m + 2 行。
第 1 行只包含一个整数 n，表示代理服务器的个数。
第 2行至第n + 1行每行是一个字符串，表示代理服务器的 IP地址。这n个 IP地址两两不相同。
第 n + 2 行只包含一个整数 m，表示要访问的服务器的个数。
第 n + 3 行至第 n + m + 2 行每行是一个字符串，表示要访问的服务器的 IP 地址，按照访问的顺序给出。
每个字符串都是合法的IP地址，形式为“xxx.yyy.zzz.www”，其中任何一部分均是0–255之间的整数。输入数据的任何一行都不包含空格字符。
其中，1<=n<=1000，1<=m<=5000。
输出描述
可能有多组测试数据，对于每组输入数据， 输出数据只有一行，包含一个整数s，表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的代理服务器不计入切换次数中。若没有符合要求的安排方式，则输出-1。
示例：
输入
3
166.111.4.100
162.105.131.113
202.112.128.69
6
72.14.235.104
166.111.4.100
207.46.19.190
202.112.128.69
162.105.131.113
118.214.226.52
输出
1
分析
这道题是一道典型的贪心算法问题，主要问题是怎么贪。首先来看一下输出-1的情况，这个很容易想到，只有一个代理服务器的时候，并且需要访问的服务器中包含这个唯一的代理服务器时，就不满足条件。只要有两个及以上的代理服务器，就一定有某种顺序能够访问完所有的服务器。就拿两个为例，只需要在这两个代理服务器中不断切换即可，这里不再多说，仔细想想就能理解。
我们主要来关注怎么贪心的问题。其实也很容易想到，从第一台服务器开始访问，如果需要访问的服务器IP地址，也是其中某一台代理服务器的IP地址，那么就对这个代理服务器做一个标记，意思是最开始选择的代理服务器不是这一台，因为如果选择这一台代理服务器，很快就需要切换了。要使切换代理服务器的次数最少，我们就需要在每一轮切换时，使得切换来使用的代理服务器能够访问更多的服务器，也就是贪心。所以按照上面的做法，依次对代理服务器进行标记，直到还剩最后一台代理服务器没有被标记，那么就选择这台代理服务器用于访问，接着继续遍历，直到最后这一台代理服务器也需要进行标记。然后如果服务器没有遍历完，那么就清空状态，记录切换次数，从下一台服务器开始，继续上述过程，直到所有服务器都遍历一遍，即可求出结果。如果第一轮遍历就已经把服务器遍历完了，那么就说明不需要切换服务器，这时没有被标记的代理服务器都可以选择用来进行访问服务器。
思路大概就是这样，不过具体在编程时还会有一些细节问题。怎么知道是不是只剩一个代理服务器没有被标记？这个可以使用一个变量来记录，最开始变量赋值为代理服务器的数量，如果有代理服务器被标记，那么变量值减1，最后如果变量值为1，并且最后一台代理服务器也需要进行标记，就说明这轮遍历结束了。另外还有一点需要注意，当遍历完一轮需要清理状态时，不要忘记在状态重置后，将上一轮最后一个未被标记的代理服务器进行标记，并且记录标记数量的变量不是设置为第一轮的n，而是n-1。因为这台被选择的代理服务器，是作为上一轮的选择，在这一轮中不能被选择。如果在这一轮中最后也被选中的话，不是相当于没有切换代理服务器吗？所以这一点也需要注意，后面的几轮遍历与第一轮的遍历略微有点区别。
AC代码如下：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//find函数
#include<cstring>//memset函数using namespace std;int main(void)
{
int n, m;string temp;while(cin >> n){
vector<string> strn, strm;//分别存储代理服务器和服务器int result = 0;//记录结果bool flag = true;//表示是否不满足条件，输出-1的标志//记录代理服务器是否被标记，题目没有要求输出切换的代理服务器//这里为什么需要做记录呢？因为有的代理服务器在需要访问的列表中出现多次//在记录时只需要记录一次即可，否则用来记录的变量会出错//这里还可以使用bool数组int* dai = new int[n];memset(dai, 0, n*sizeof(int));for(int i = 0; i < n; ++i){
cin >> temp;strn.push_back(temp);dai[i] = 0;}cin >> m;int left = n;//记录还未被标记的代理服务器数目int index = 0;//记录vector中的元素下标for(int i = 0; i < m; ++i){
cin >> temp;//如果不满足条件就没必要继续下去浪费运行时间//不过输入还没有结束，不能直接break出去输出//至少要等到程序的输入完成if(flag == false){
continue;}strm.push_back(temp);//泛型查找函数，很好用//如果类型名称过长，可以使用auto自动推断类型vector<string>::iterator it = find(strn.begin(), strn.end(), temp);if(it != strn.end())//表示找到了{
//这是在vector中返回迭代器所指向的元素的下标的常用手段//使用当前迭代器减去起始迭代器//即是当前迭代器所指向的元素的下标index = it - strn.begin();if(dai[index] == 0)//代理服务器未被标记{
dai[index] = 1;--left;}}if(left == 0){
//所以代理服务器都需要被标记，并且输入只有一个代理服务器//说明肯定不满足条件，需要输出-1if(n == 1){
flag = false;continue;}++result;//重置状态memset(dai, 0, n*sizeof(int));//最后一个被标记的代理服务器不能参与下次循环dai[index] = 1;left = n - 1;}}delete [] dai;if(flag){
cout << result;}else{
cout << -1;}}return 0;
}