想象一下,代理服务器是一个漏筛,漏筛的每一个洞代表一个代理服务器地址,而待访问的服务器序列要经过这个漏筛,每一次待访问的服务器如果和其中的一个洞相同,则堵上该洞。这样就保证了每一段都选择尽可能多重复使用的地址,降低跳转次数。
当洞被堵满,有两种情况:
1.当前待访问的服务器地址和所有代理服务器地址全部相同,即没有可用的代理服务器,应该返回-1。(其实本题明确告知代理服务器地址两两不同,故只有一种可能,那就是只有一个代理服务器地址,并且这个地址中枪了)
2.历史沉淀,一层一层筛选之后,某一个地址将最后一个可用的代理服务器地址给重合了。这个时候需要跳转一次,将之前所有堵上的洞重新释放,进入新一段的过筛。但是这个洞要堵上,成为历史遗留。
//试题:https://www.nowcoder.com/questionTerminal/1284469ee94a4762848816a42281a9e0
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int func(string agentip[],string realip[],int agentnum,int realnum,int avoid0[],int realnow){
if(realnow >= realnum) return 0;
int avoidnow[agentnum];//标记数组,当前待访问服务器与代理服务器组之间的映射关系
int rowsum_n = 0;//标记值,如果rowsum_n = agentnum,则说明无可用的代理服务器
int rowsum = 0;//标记值,如果rowsum = agentnum,则说明需要进行一次跳转
for(int i = 0;i < agentnum;i++){
if(agentip[i] == realip[realnow]){
rowsum_n++;
avoidnow[i] = 1;
}
else avoidnow[i] = 0;
if(avoid0[i] != avoidnow[i]) avoid0[i] = 1;
if(avoid0[i]) rowsum++;
}
if(rowsum_n == agentnum) return -1;
int change = 0;
if(rowsum != agentnum) change =func(agentip,realip,agentnum,realnum,avoid0,realnow+1);
else{
change = func(agentip,realip,agentnum,realnum,avoidnow,realnow+1);
if(change != -1) change++;
}
return change;
}
int main(){
int agentnum;
int realnum;
int i,j;
while(scanf("%d",&agentnum) != EOF){
string agentip[agentnum];
for(i = 0; i < agentnum; i++)
cin >> agentip[i];
int avoid0[agentnum];
for(i = 0; i< agentnum;i++) avoid0[i] = 0;
scanf("%d",&realnum);
string realip[realnum];
for(i = 0; i < realnum; i++){
cin >> realip[i];
}
int change = func(agentip,realip,agentnum,realnum,avoid0,0);
printf("%d",change);
}
return 0;
} 
京公网安备 11010502036488号