题解 | #代理服务器#

贪心+二分查找

首先将ip地址字符串映射到int域内，通过map实现。 然后预处理，将每个服务器的ip对应值存到数组中。 最后按照贪心+二分查找的思想即可。 具体的： 1、只有当代理服务器数量为1，并且在服务器序列中出现该代理服务器ip地址时，没有符合条件的分配策略，此时返回-1； 2、对于其他情况，当前选择一个代理服务器，应当贪心的选择可以匹配服务器的最大数量，然后再切换代理服务器，同样也是选择可以匹配最大数量的代理服务器。

代码：

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int ag[1005],se[5005];//代理服务器和服务器
map<string,int>mp;
vector<vector<int> >v;
int cnt;
void init(int m,int n){
    v.resize(cnt+5);
    for(int i=1;i<=m;++i){
        v[se[i]].emplace_back(i);
    }
    for(int i=1;i<=cnt;++i)    v[i].emplace_back(m+1);
}
int solve(int n,int m){
	//maxx和idx是当前选择的代理服务器可以匹配到的服务器序列号以及代理服务器编号
    int ans=0;
    int maxx=-1,idx=-1;
    for(int i=1;i<=n;++i)    {
        if(v[ag[i]][0]>maxx)    maxx=v[ag[i]][0],idx=i;
    }
    while(maxx<=m){
        ans++;
        int maxt=-1,id=-1;
        for(int i=1;i<=n;++i){
            if(i==idx)    continue;
            //二分查找，速度更快
            auto t=lower_bound(v[ag[i]].begin(),v[ag[i]].end(),maxx);
            if(t!=v[ag[i]].end()){
                if(*t>maxt)    maxt=*t,id=i;
            }
        }
        //重新选择代理服务器
        maxx=maxt,idx=id;
    }
    return ans;
    
}
int main(){
    int n,m;
    string s;
    while(~scanf("%d",&n)){
    	//map映射
        for(int i=1;i<=n;++i){
            cin>>s;
            mp[s]=++cnt;
            ag[i]=cnt;
        }    
        scanf("%d",&m);
        for(int i=1;i<=m;++i){
            cin>>s;
            auto t=mp.find(s);
            if(t!=mp.end()){
                se[i]=(*t).second;
            }else{
                mp[s]=++cnt;
                se[i]=cnt;
            }
        }
        init(m,n);
        //特殊情况，没有符合要求的分配方案
        if(n==1&&v[ag[1]][0]!=m+1)    printf("%d\n",-1);
        else printf("%d\n",solve(n,m));
    }
}