题解 | 代理服务器

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;

map<string,int> proxy;
vector<string> target;

bool full(){
    for(pair p:proxy){
        if(p.second==0)return false;
    }
    return true;
}

int main() {
    int m,n;
    while (cin >> m) { 
        string tem;
        int res=0;//修改次数
        for(int i=0;i<m;i++){
            cin>>tem;
            proxy[tem]=0;
        }
        cin>>n;
        for(int i=0;i<n;i++){
            //cin>>target[i];  这种初始化方式是错误的，因为定义vector时并没有给定初始长度，所以长度默认是0；没办法通过target[i]去访问一个空的容器；
            cin>>tem;
            target.push_back(tem);
        }
        for(int i=0;i<n;i++){
            string str=target[i];
            auto it = proxy.find(str);
            if(it!=proxy.end()){
                it->second++;
                if(full()){
                    res++;
                    for(auto& p:proxy){
                        p.second=0;
                    }
                    it->second++;
                }
            }
        }
        if(res==n)cout<<-1;
        else cout<<res;
    }
}
// 64 位输出请用 printf("%lld")

这里搬运了三个优质题解，并综合了一下，其实原理都是相同的；

【算法思路】：

首先读入所有的代理服务器，用map<string, int>存储，int表示每个代理ip被使用的次数，初始设0。然后依次读入需要访问的服务器，读入一个地址后判断是否存在在代理服务中，如果存在，将该地址的代理使用次数+1，并判断是否全部的代理ip使用次数都大于0，如果全部都大于0，那说明，需要变更代理服务器了，则变更次数+1，然后将所有代理ip的使用次数重置为0，并将当前的代理ip次数加1；

【原理】：贪心

依次访问服务器ip，遇到和代理ip相同的则标记一下，

直到遇到一个代理A时全部代理都被标记过，这时认为之前都是用这个代理A进行访问的，

此时切换代理（次数+1）并清零A以外的标记，同样的，遇到代理标记一下，

直到遇到一个代理B时全部代理都被标记过，这时认为之前都是用这个代理B进行访问的，

切换代理（次数+1），以此类推……

【分析】：

其实就是要尽可能使用和要访问服务器没有交集的代理服务器。

如果要访问的服务器中没有和代理服务器 IP 相同的，则返回 0；

如果有相同的，那么每个代理服务器都在某一个位置相同，比如例子中的分别在 1、4、2 处相同，那么贪心策略就是每次找一个和代理ip相同的的服务器ip，且该ip加上之前所有相同的ip组成的集合第一次覆盖了所有代理ip；并认为之前的服务器都是用该代理ip访问的，到了他这里该换ip了；然后以这个服务器为起点在剩余的服务器中，接着上述操作；