代理服务器
这道题思路很容易就能想到,比如代理服务器为1,2,3;服务器为4,1,5,3,2,6。从服务器访问顺序开始,看哪台代理服务器能访问最久,很明显上述例子中代理服务器2能访问最久。这样,服务器4,1,5,3都用代理服务器2访问,从2开始服务器2,6用除2外的代理服务器访问(所以切换次数为1).
本题的难点是代码实现,如何找到代理服务器在服务器中能走得最远的位置,下面的代码是我参考别人,注释是我参考别人的代码后再结合自己原来的做法作出的思考:
#include <iostream> #include<string> using namespace std; int main() { int n, m, i; while (cin >> n) { string *proxy = new string[n]; for (i = 0; i < n; ++i) cin >> proxy[i]; cin >> m; string *server = new string[m]; for (i = 0; i < m; ++i) cin >> server[i]; //找代理服务器能在服务器列表中走的最远的距离 bool arrive = 1; if (n == 1) {//只有一台代理服务器的情况,显然,如果服务器中包含了该代理服务器,那么没有可行方案 for (i = 0; i < m; ++i) { if (server[i] == proxy[0]) { arrive = 0; break; } } if (arrive) cout << 0; else cout << -1; continue; } int cursor = 0, max = 0, count = 0, j = 0; //cursor记录访问到了哪台服务器,max记录本轮(某次代理切换后)代理服务器能走的最远距离,,count记录轮数(所以count比切换数多1) while (cursor < m) { for (i = 0; i < n; ++i) { for (j = cursor; j < m; ++j) { if (server[j] == proxy[i]) { break; } } if (j > max)//开始时我是把这一步放到了j的for循环的if语句中,这样的话,若是某轮并不是所有代理服务器都在访问的服务器中,那么max记录的只是某台代理服务器能访问的最远距离,而不是全部代理服务器能走的最远距离 max = j; } cursor = max; ++count; } cout << count - 1; } system("pause"); return 0; }