想象一下,代理服务器是一个漏筛,漏筛的每一个洞代表一个代理服务器地址,而待访问的服务器序列要经过这个漏筛,每一次待访问的服务器如果和其中的一个洞相同,则堵上该洞。这样就保证了每一段都选择尽可能多重复使用的地址,降低跳转次数。
当洞被堵满,有两种情况:
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; }