牛客网：代理服务器：stl快速实现最优页面调度算法_服务器广播算法牛客网

题目大意

使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器，并要求不能用代理服务器去访问和它 IP地址相同的服务器（不然客户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方案，使得代理服务器切换的次数尽可能得少。

思路分析

利用set，map，string迅速完成最优页面调度算法。首先将所有可用服务器ip存入map。然后按序输入每一个待访问的ip，对每一个ip如果他是我们map中的一员，那么把他insert到set对象中，由于set良好的去重特性，当set集合的大小==map的大小的时候，说明我们已经把所有代理ip用光了，此时将set对象clear，重新进行新的一轮计数。

• 最后一个用掉的ip在下一次循环时不能使用，考虑我们只有a,b两个ip，访问序列为a b a b，第一次我们到b的时候必须转换了，此时说明我们一开始用的是b，所以这里必须选另一个ip a来进行访问。（自己手推一遍就懂了）
• 注意不能得出结果的情况，就是只有一个ip而且还发生了冲突。

#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

#define MAX 1005
#define ll int

map<string, ll> m;
ll N, M;

int main() {
	while (cin >> N) {
		m.clear();
		string s1; 
		for (int i = 0; i < N; i++)
		{
			cin >> s1; m[s1] = 1;
		}
		cin >> M; ll res = 0, cnt = m.size();
		set<string> sets;
		for (int i = 0; i < M; i++) {
			cin >> s1;
			if (res == -1)continue;
			if (m.find(s1) != m.end()) {//有这个元素
				sets.insert(s1);//插入集合中,表示该元素这一轮用过了
			}
			if (sets.size() == cnt) {//所有的ip都用了，在这里需要更换一次了
				sets.clear(); res++; sets.insert(s1);//最后活着的这个s1本次循环用了
				if (cnt == 1) { res = -1; continue; }//只有一个元素而且有冲突
			}
		}
		cout << res << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38