首页 > 试题广场 >

代理服务器

[编程题]代理服务器
  • 热度指数:31569 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    使用代理服务器能够在一定程度上隐藏客户端信息,从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址,现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器,并要求不能用代理服务器去访问和它 IP地址相同的服务器(不然客户端信息很有可能就会被泄露)。在这样的条件下,找到一种使用代理服务器的方案,使得代理服务器切换的次数尽可能得少。

输入描述:
    每个测试数据包括 n + m + 2 行。
    第 1 行只包含一个整数 n,表示代理服务器的个数。
    第 2行至第n + 1行每行是一个字符串,表示代理服务器的 IP地址。这n个 IP地址两两不相同。
    第 n + 2 行只包含一个整数 m,表示要访问的服务器的个数。
    第 n + 3 行至第 n + m + 2 行每行是一个字符串,表示要访问的服务器的 IP 地址,按照访问的顺序给出。
    每个字符串都是合法的IP地址,形式为“xxx.yyy.zzz.www”,其中任何一部分均是0–255之间的整数。输入数据的任何一行都不包含空格字符。
     其中,1<=n<=1000,1<=m<=5000。


输出描述:
    可能有多组测试数据,对于每组输入数据, 输出数据只有一行,包含一个整数s,表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的代理服务器不计入切换次数中。若没有符合要求的安排方式,则输出-1。
示例1

输入

3
166.111.4.100
162.105.131.113
202.112.128.69
6
72.14.235.104
166.111.4.100
207.46.19.190
202.112.128.69
162.105.131.113
118.214.226.52

输出

1
做的时候总感觉贪心得不到最优解,没想到竟然过了。。
讨论区好像没有证明,我就照着模板写了一个证明(第一次写证明可能说的不是很清楚,老哥们有更精炼的证明希望可以发一下)

证明如下:
假设有一个列表存储所有***服务器IP,称为proxy,另一个列表存储要访问的服务器IP序列,称为target

从头到尾遍历target列表,并记录其中***服务器IP出现的情况。当proxy中的每一个IP都出现一次(我称其为一个周期),下一次再出现***服务器IP时就必须要更换***服务器。

所以我们的贪心策略就是,每次都选择在一个周期中最后出现的***服务器作为切换的目标***服务器,比如说初始***服务器就是目标服务器列表的第一个周期中最后一个***服务器。

假设贪心算法结果为A,如果A不是最优,那么一定存在一个最优解OOA至多前k-1个选择相同,从第k个选择开始不同。

这里的第k个选择就是第k次切换***服务器时选择作为替换目标的***服务器IP

假设对于AAk次切换选择的是第s个***,而O中第k次选择第s’个***。我们再构建一个解O’,其前k-1个选择与O相同,k之后的选择也与O相同,只有第k个选择变为第s个***。

由于在第k个位置选择第s个***,其切换的必须位置在选择s‘时之后,所以其切换的次数和O相同,O’仍为最优解,但是O’与A的共同选择有k个,这与我们的前提最多k-1个共同选择相冲突。从此向后递推可得出A为最优解。

发表于 2019-05-07 23:47:25 回复(0)
更多回答
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(){
    int n=0,m=0;
    int terminal=0;
    vector<string> a;
    vector<string> b;
    string temp;
    while(cin>>n){//录入数据
    for(int i=0;i<n;i++){
     cin>>temp;
     a.push_back(temp);        
    }
    cin>>m;
    for(int i=0;i<m;i++){
    cin>>temp;
    b.push_back(temp);   
    }       
  if(n==1) {//只有1个***
      for(int i=0;i<m;i++){
       if(a[0]==b[i]){
       cout<<-1<<endl;
       break;
       }
       else if(i==m-1)cout<<0<<endl;
      }
     
  } 
  else{  //多个***
    int count=0;//目前访问到第几个服务器
    int countnei=0;
    int max=-1;
    int whichone=-1;//目前在用哪个***服务器线路
    while(count!=m){//访问服务器没到最后则持续执行
    for(int i=0;i<n;i++){//***服务器轮流判断最长不需换路步数
        if(i==whichone)continue;
    for(int j=count;j<m;j++){ //判断步数取最长   
    if(a[i]==b[j]){
     if(max<j-count){
        max=j-count;
        whichone=i;
        if(j>countnei)countnei=j;}
        break;
    }
    else if(j==m-1){
        count=m;
        break;
    }
    }
    }    
    if(count!=m){terminal++;
    count=countnei;            
    }
    max=-1;
    }  
    cout<<terminal<<endl;
    terminal=0;
  }
    a.clear();
    b.clear();
    }
    return 0;
} 
这个问题主要是每次哪个判断***服务器能持续走最长(局部最优),然后再从换路的地方再算哪个
持续走最长,依次下去。贪心即最优,可用数学证明。

发表于 2017-02-24 19:47:14 回复(2)
#include <stdio.h>
#include <string.h>

#define MAXN  16

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        char agent[n][MAXN];
        for(int i = 0; i < n; i++){
            scanf("%s", agent[i]);
        }
        int m;
        scanf("%d", &m);
        char server[m][MAXN];
        for(int j = 0; j < m; j++){
            scanf("%s", server[j]);
        }  //以上为输入部分

        if(n == 1 ){
            for(int i = 0; i < m; i++){
                if(!strcmp(agent[0], server[i])){
                    printf("-1\n");
                    break;
                }
            }
        }//无符合安排方式判定时输出 -1 并跳出;
        else{
            int flag[n];
            int cnt = 0, ans = 0;
            memset(flag, 0, sizeof(flag));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(!strcmp(server[i], agent[j])){
//若用户服务器和当前的代理服务器相同。则标记并计数器加一;
//若已标记过,则计数器不再加一;
                        if(flag[j] == 0){
                            flag[j] = 1;
                            cnt++;
                        }
                    }
//若n个代理服务器已全被标记,则表示找到最远相同的代理服务器,则转换次数加 1;
                    if(cnt == n){
                        j--;                            //除去最后一个相同的,并从这儿重新开始
                        ans++;
                        cnt = 0;                        //计数清零
                        memset(flag, 0, sizeof(flag));  // 重置flag数组;
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

编辑于 2021-03-23 21:00:54 回复(0)
贪心策略:从0开始向后遍历,不考虑之前选了什么,在n个***服务器都出现的时间点,贪心的认为之前的时间段里用了最后出现的ip地址编号。下一个时间段选择剩下的n-1个服务器中最后出现的ip编号。
//include .... using namespace std;
char ip[1005][16], todo[5005][16];//ip是***,todo是访问服务器
bool used[1005];  //某时间段是否某***ip是否出现过
int usednum;//开始usednum记成了bool类型,调了好久 int main()
{  /*...读入,此题%s即可...*/
        int ans = 0; //切换次数
        for(int i = 0; i < m; i++){//访问服务器指针
            for(int j = 0; j < n; j++){//***ip指针
                if(strcmp(ip[j], todo[i]) == 0){ 
                    if(used[j] == 0){
                        used[j] = true; usednum++; //第一次出现此ip,修改记录
                        if(usednum == n){ //所有***ip号都出现了
                            ans++;
                            usednum = 0; memset(used, false, sizeof(used));
                            usednum = 1; used[j] = true; //下个时段选与此时不同的***ip
                        }
                    }break;//只会有一个匹配,节省时间
                }
            }
        }
        if(n == 1 && ans != 0)printf("-1\n");//唯一不符合的情况
        else printf("%d\n", ans);
}

编辑于 2018-07-09 02:54:10 回复(1)

超时代码,请大佬帮忙剪纸啊

import java.util.Scanner;

/** 
*
* @author special
* @date 2017年12月19日 上午10:15:23
*/
public class Main {
    private static String[] proxys;
    private static String[] server;
    private static int min;

    public static void dfs(int index, String proxy, int count){
        if(index == server.length){
            if(count < min) min = count;
            return;
        }
        if(proxy.equals(server[index])){
            for(int i = 0; i < proxys.length; i++){
                if(!proxys[i].equals(proxy)){
                    dfs(index + 1, proxys[i], count + 1);
                }
            }
        }else{
            dfs(index + 1, proxy, count);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            proxys = new String[n];
            for(int i = 0; i < n; i++)
                proxys[i] = input.next();
            int m = input.nextInt();
            server = new String[m];
            for(int i = 0; i < m; i++)
                server[i] = input.next();
            min = Integer.MAX_VALUE;
            for(int i = 0; i < n; i++){
                if(!proxys[i].equals(server[0])){
                    dfs(1,proxys[i],0);
                }
            }
            System.out.println(min == Integer.MAX_VALUE ? -1 : min);    
        }
    }

}
发表于 2017-12-19 10:53:17 回复(4)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int maxn=1000;
const int maxm=5000;

string Start[maxn];
bool flag[maxn];
string Target[maxm];

int main(){
	int n,m;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>Start[i];
	}
	cin>>m;
	for(int i=0;i<m;++i){
		cin>>Target[i];
	}
	sort(Start,Start+n);
	for(int i=0;i<n;++i){
		flag[i]=false;
	}
	if(n==1){
		for(int i=0;i<m;++i){
			if(Start[0]==Target[i]){
				cout<<-1<<endl;
				return 0;
			}
		}
		cout<<0<<endl;
		return 0;
	}
	int count=0,result=0;
	for(int i=0;i<m;++i){
		int left=0,right=n-1;
		int mid;
		while(left<=right){
			mid=(left+right)/2;
			if(Start[mid]==Target[i]){
				if(flag[mid]==false){
					flag[mid]=true;
					count++;
				}
				break;
			}else if(Start[mid]<Target[i]){
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		if(count==n){
			result++;
			count=1;
			for(int j=0;j<n;++j){
				flag[j]=false;
			}
			flag[mid]=true;
		}
	}
	cout<<result<<endl;
	return 0;
}

发表于 2022-08-01 20:54:55 回复(0)

解题思路

贪心。对于请求访问的IP序列,忽略其他IP地址,记录代理服务器地址。如果某处正好出现全部代理服务器地址,说明之前的访问可以通过同一个代理服务器完成,并且此时需要转换。所以ret+1,清空之前的记录表,并且加入当前的IP地址
另外注意特判代理服务器长度为1的情况。若代理服务器长度为1,且请求过程出现代理服务器地址,则结果为-1,否则为0。不过这题的点并没有测试为0的情况。

代码

set优化查询。
#include <cstdio>
#include <vector>
#include <set>
#include <string>

using namespace std;

int main() {
    int n, m;
    set<string> ips;
    // read in
    scanf("%d", &n);
    char buf[50];
    for (int i = 0; i < n; i++) {
        scanf("%s", buf);
        ips.insert(string(buf));
    }
    // comp
    set<string> S;
    string temp;
    int ret = 0;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%s", buf);
        temp = buf;
        if (ret < 0)
            continue;
        if (ips.count(temp) <= 0) // other ip
            continue;
        if (ips.size() <= 1) {
            ret = -1;
            continue;
        }
        S.insert(temp);
        if (S.size() >= n) {
            S.clear();
            S.insert(temp);
            ret++;
        }
    }
    printf("%d\n", ret);
    return 0;
}
发表于 2021-04-04 12:20:50 回复(0)
.备注应该写清楚了,只有一段关键代码
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std; int main()
{
	vector<string> agent, visit;
	int n, m;
	string temp;
	while (cin >> n)
	{
		int i;
		for (i = 0; i < n; i++)//输入代理服务器
		{
			cin >> temp;
			agent.push_back(temp);
		}
		cin >> m;
		for (i = 0; i < m; i++)//输入访问服务器顺序
		{
			cin >> temp;
			visit.push_back(temp);
		}
		//pos:需要改变代理的服务器位置,count:改变次数
		int pos = 0, count = 0;
		//find函数查找的迭代器
		vector<string>::iterator it, start = visit.begin(), flag;
		//需要改变代理的服务器IP
		string current = "";

		//关键代码段
		//当只有一台代理,且要访问自己时,无论如何都要自己代理自己
		if (n == 1 && find(visit.begin(),visit.end(),agent[0]) != visit.end())
			count = -1;
		else
		{
			while (pos != visit.size())
			{//每一趟查找在服务器中最后访问的代理服务器位置
				for (i = 0; i < n; i++)
				{
					if (agent[i] != current)
					{
						it = find(start, visit.end(), agent[i]);
						int p = it - visit.begin();//用int型判断大小(前后位置)
						if (p > pos)
						{
							pos = p;
							flag = it;
						}
					}
					else
						continue;
				}
				//下一趟查找从当前下个位置开始;查找除了当前IP的所有代理服务器位置
				if (pos != visit.size())
				{
					start = ++flag;
					current = visit[pos];
					count++;
				}
			}
		}
		cout << count << endl;
		agent.clear();
		visit.clear();
	}
	return 0;
}

编辑于 2020-06-06 11:55:17 回复(0)
/*代理服务器用ipn[n]存储,要访问的服务器用ipm[m]存储,对于每一个要访问的服务器,将其与每一个代理服务器比较,
,设置judge[n]全为0,若相同则对应judge[]为1,judge全1时,代表这一轮在此之前都使用这一服务器,并且此时代理服务器
ip与要访问服务器ip相同,要切换服务器,因此切换次数count++,然后judge[]重置为0,但是judge[当前服务器位置]为1
(视为切换服务器后碰到的第一个服务器)。ps:注意只有一个代理服务器时情况*/
#include<stdio.h>
(737)#include<string.h>
#define N 20
int reset(int a[],int n)
{
    for(int i=0;i<n;i++)
    a[i]=0;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
	char ipn[n][N];
	for(int i=0;i<n;i++)
	{
            scanf("%s",ipn[i]);
	 }
	int m;
	scanf("%d",&m);
	char ipm[m][N];
	for(int i=0;i<m;i++)
	{
	    scanf("%s",ipm[i]);
	 }
		
	int judge[n];
	reset(judge,n);
	int flag=0;					//判断judge是否变化 
	int count =0;					//转换服务器次数 
	int flag_n=0;					//n=1时发生匹配则跳出循环,输出-1 
	for(int i=0;i<m;i++)
	{
	    for(int j=0;j<n;j++)
	    {
		if(!strcmp(ipm[i],ipn[j])) 	//ipm[]与ipn[]匹配 ,则judge[]置1 
		{
		    judge[j]=1;					
		    flag=1;					
		 }
		if(flag==1)			//judge[]位变动则判断是否全为1(即是否全部轮过一遍) 
		{
		    if(n==1)
		    {
			printf("-1\n");
			flag_n=1; 
			break;
		     }
		    int flag2=0;				//有0说明还有未轮过,跳出 
	   	    for(int k=0;k<n;k++)
		    {
			if(judge[k]==0)
			{
			    flag2=1;
			    break;
			 } 
		     }
		    if(flag2==0)
		    {
			count++;
			reset(judge,n);
			judge[j]=1;
			flag=0; 
			break;				//有重复就对下一个ipm进行匹配,因为ipn各不相同,只可能匹配成功一个 
		     }
		    else flag=0; 					
		}
	    }
	    if(flag_n==1) break;	
	}
	if(flag_n==0) printf("%d\n",count);
	flag_n=0;
    }
    return 0;
}

发表于 2020-03-31 21:52:56 回复(0)
#include <iostream>
#include <algorithm>
#include <map>

// AC in Mar 11th, 2020.
// Time: 4mm
using namespace std;
int main() {
    int n, m, answer = 0;
    cin>> n;
    string proxy[n];
    map<string, int> pair;
    int left = n;
    for (int i = 0; i < n; ++i) {
        cin>> proxy[i];
        pair.insert({proxy[i], 0}); // set to the  NOT FOUND state.
    }
    cin>> m;
    string server[m];
    for (int j = 0; j < m; ++j) {
        cin>> server[j];
    } // end of input

    for (int k = 0; k < m; ++k) {
        if (!binary_search(proxy, proxy + n, server[k])) { // not in the proxy list.
            continue;
        } else if (pair[server[k]] == 1) { // in the proxy list but value of pair is 1.
            continue;
        } else { // in the proxy list and value of pair is 0.
            pair[server[k]] = 1; // set to the FOUND state.
            left--;
        }

        if(left == 0) { // a circle.
            left = n - 1; // not including the current one.
            for (int i = 0; i < n; ++i) {
                pair[proxy[i]] = 0; // reset to the initial state.
            }
            pair[server[k]] = 1; // not including the current one.
            answer++; // all the proxy were found, so plus 1.
        }
    }

    if(n == 1 && binary_search(server, server + m, proxy[0])) {
        answer = -1; // special answer
    }
    cout<< answer;
    return 0;
}

这是一道贪心算法的题目。解法就是“画圈”,从头开始,把所有的proxy都找到,answer++,这里很重要的一点就是,画下一个圈的时候,要从上一个“圈的末尾”开始,所有的“圈”要连成一环,而不是从下一个结点开始。
编辑于 2020-03-11 11:33:37 回复(0)
#include <cstdio>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
    int n, m, cnt = 0;
    char buf[16];
    unordered_map<string, bool> proxy; //代理服务器列表及其是否出现记录表
    vector<string> server; //服务器队列
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", buf);
        proxy[string(buf)] = false;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%s", buf);
        server.push_back(string(buf));
    }
    //代理服务器只有一台的情况下,查找服务器列表里边有没有代理服务器,有就无解返回
    if (n == 1) {
        string only_proxy = proxy.begin()->first;
        for (const auto& s : server) {
            if (s == only_proxy) {
                printf("-1\n");
                return 0;
            }
        }
    }
    //遍历请求服务器队列
    for(const auto& s: server){
        //此服务器为代理服务器之一时,开始对比服务器出现记录表
        if (proxy.find(s) != proxy.end()) {
            proxy[s] = true;
            bool all_true_flag = true;
            for (const auto& x : proxy) {
                if (!x.second) {
                    all_true_flag = false;
                    break;
                }
            }
            //所有服务器都出现过时,切换次数加一,当前遍历到的服务器为上一次切过来的代理服务器,此时应切出此服务器到另外一个代理服务器上
            if (all_true_flag) {
                cnt++;
                for (auto& i : proxy)
                    i.second = false;
                //因为是从当前服务器切出的,切入的下一个服务器不应为当前服务器,当前服务器出现计为true,其余计为false
                proxy[s]=true;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

编辑于 2020-03-12 00:29:56 回复(0)
/*
`    这是一道考察贪心策略的问题,每次遍历一遍proxy服务器数组,计算他们在当前的服务器序列中可以访问的最大服务数量
    下次继续遍历所有proxy服务器的话就直接从上次记录的最大可访问的服务器数下标开始再次遍历就行了
    注释写得比较详细,大家可以看看
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
const int MAXM = 5010;
string proxy[MAXN];
string server[MAXM];
int main(){
	int n,m;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>proxy[i];
		}
		cin>>m;
		for(int i=0;i<m;i++){
			cin>>server[i];
		}
		int index = 0; //用来记录当前要从服务器数组访问的下标
		int count = -1;// 记录切换次数
		int flag = 1; // 记录proxy服务器访问服务器的成功标志
		while(flag==1&&index!=m){
			int max = 0; // 记录遍历从index位置开始遍历一遍proxy服务器后可访问的服务器数量
			for(int i = 0 ;i<n;i++){
				int j = index; // 服务器的位置从上次可以访问的最大数量的下标开始
				while(proxy[i]!=server[j]&&j<m){
					j++;
				}
				if(j-index>max){
					max = j-index;
				}
			} 
			count++; // 切换次数增加
			if(max == 0){ //如果遍历一遍proxy服务器但是最大可访问数量为0,则认为无解 
				flag = 0;
			}else{
				index+=max;
			}
		}
		if(flag){ 
			cout<<count<<endl;
		}else{ 
			cout<<-1<<endl;
		}
	}
    return 0;
}

发表于 2020-03-08 09:15:43 回复(0)
#include <stdio.h>
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        int m;
        unsigned proxy[1000];
        unsigned server[5000];
        unsigned a,b,c,d;
        for(int i=0; i<n; i++) {
            scanf("%d.%d.%d.%d",&a,&b,&c,&d);
            proxy[i]=a*256*256*256+b*256*256+c*256+d;
        }
        scanf("%d",&m);
        for(int i=0; i<m; i++) {
            scanf("%d.%d.%d.%d",&a,&b,&c,&d);
            server[i]=a*256*256*256+b*256*256+c*256+d;
        }
        int count=0;
        if(n==1) {
            for(int i=0; i<m; i++) {
                if(server[i]==proxy[0]) {
                    count=-1;
                    break;
                }
            }
        } else {
            int mark_proxy[1000]= {0};
            int mark=0;
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(proxy[j]==server[i]) {
                        if(mark_proxy[j]==0) {
                            if(mark==n-1) {
                                count++;
                                for(int k=0; k<n; k++) {
                                    mark_proxy[k]=0;
                                }
                                mark=0;
                            }
                            mark_proxy[j]=1;
                            mark++;
                        }
                        break;
                    }
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

发表于 2020-03-03 21:20:30 回复(0)
#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

int main(){
	int m,n;
	unsigned int a,b,c,d;
	unsigned int vec[1001];
	unsigned int exm[2000];
	map<unsigned int,bool> ma;//标记代理ip是否被统计

	while(scanf("%d",&n)!=EOF && n!=0){
		memset(vec,0,sizeof(vec));
		memset(exm,0,sizeof(exm));
		for(int i=0;i<n;i++){
			scanf("%d.%d.%d.%d",&a,&b,&c,&d);
			vec[i] = ((a<<8|b)<<8|c)<<8|d;   //转化为unsigned int类型整数表示ip
		}
		sort(vec,vec+n);

		scanf("%d",&m);
		for(int i=0;i<m;i++){
			scanf("%d.%d.%d.%d",&a,&b,&c,&d);
			exm[i] = ((a<<8|b)<<8|c)<<8|d;   //转化为unsigned int类型整数表示ip
		}
		//输入结束

		//贪心算法
		ma.clear();
		int temp=n;
		int ans =0;
		for(int i=0;i<m;i++){   //逐一考察每个服务器
			if(binary_search(vec,vec+n,exm[i])){  //如果该服务器ip是代理ip之一

				//贪心找到能访问最多服务器的代理ip
				if(!ma[exm[i]]){      //该代理ip未被统计
					if(temp==1){          //且其他代理ip都以被统计,那么该代理IP为目前选定的代理ip地址
						ans++;
						ma.clear();
						temp=n;
					}
					ma[exm[i]]=true;
					temp--;
				}
			}
		}

		//返回-1情况
		if(n==1 && ans > 0) {
			cout<<-1<<endl;
			continue;
		}
		cout<<ans<<endl;
	}

	return 0;
}


贪心算法
运行时间:4ms
占用内存:592k
时间复杂度:mlogn
空间复杂度:m+n
编辑于 2020-02-23 17:53:54 回复(0)
//典型贪心算法
//要找到访问服务器地址中最后出现的***服务器
#include<iostream>
#include<string>
#include<string.h>
#include<vector>
using namespace std;
int main(){
    int n1,n2,num=0,count=0,a[9000];
    memset(a,0,sizeof(a));
    while(cin>>n1){
        string str;
        vector<string> vi;
        vector<string> v;
//存***服务器
        for(int i=0;i<n1;i++){
            cin>>str;
            vi.push_back(str);
        }
//存访问服务器
        cin>>n2;
        for(int i=0;i<n2;i++){
            cin>>str;
            v.push_back(str);
        }
        int num;
//遍历访问服务器
        for(vector<string>::iterator it=v.begin();it!=v.end();it++){
//a[i]用来记录***服务器是否出现过
            for(int i=0;i<vi.size();i++){
                if(*it==vi[i]){
                    a[i]=1;
                    num=i;
                }
            }
            int j=0;
//找到最远的***服务器,此时更换***服务器
            if(vi.size()>1){
                for(;j<n1;j++){
                    if(!a[j])
                        break;
                }
                if(j==n1){
                    memset(a,0,sizeof(a));
                    a[num]=1;
                    count++;
                }
            }
//如果只有一个***服务器并出现在访问服务器里,则没有办法
            else if(a[0]==1&&vi.size()==1)
                count=-1;        
        }
        cout<<count;
    }
    return 0;
}

发表于 2019-01-25 20:00:55 回复(0)
#include <iostream>
#include <string>

//此题的思路是贪心算法,先遍历每个***服务器,看***服务器能访问到的最大步长,记录下来,
//下个***继续从该位置访问,直到所有的服务器都访问完
using namespace std;
int main() 
{
    int n, m, count = 0;//count代表转换次数
    cin >> n;
    string pro[5000], ser[5000];//pro为***服务器,ser为待访问服务器
    for (int i = 0; i<n; i++) 
    {
        cin >> pro[i];
    }
    cin >> m;
    for (int j = 0; j<m; j++) 
    {
        cin >> ser[j];
    }
    int index = 0, flag = 1;//index为当前访问到的服务器,flag为是否遍历成功
    while (flag&&index != m) 
    { 
        //当游标index遍历到m时表示遍历结束
        int max = 0;//代表一个***服务器能访问到的最远步长
        for (int i = 0; i<n; i++) 
        {
            int j = index;//从游标位置开始遍历 
            while((pro[i]!=ser[j])&&(j<m)) 
                j++;//条件不满足之前一直遍历服务器 
            if(j-index>max)//寻找当前更换***点能到达的最大步长
                max=j-index; //j-index为步长
        }
        if (max == 0) 
            flag = 0;//代表遍历失败
        count++;
        index += max;//下个***从此处开始遍历 ,index每加一次max代表一个***走到了最大步长 ,count+1,直到index=m
    }
    if (flag) 
        cout << count - 1 << endl;//第一次不算转换
    else 
        cout << -1 << endl;
    return 0;
}

发表于 2018-10-14 11:28:14 回复(0)
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    string s[1000];
    string s1[5000];
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++)    cin>>s[i];
    cin>>m;
    for(int i=0;i<m;i++)    cin>>s1[i];
    int flag=0,change=0,count=0,j,max;
    while(flag<m)
    {
         max=0;
        for(int i=0;i<n;i++)
        {
            j=flag;
            count=0;
            while(j<m&& s[i]!=s1[j])
            {
                count++;
                j++;
            }    
            if(count>max)    max=count;
        }
        if(max==0)    break;
        flag+=max;
        change++;
    }
    if(max==0)    cout<<"-1";
    else cout<<change-1;    
}
 

发表于 2018-05-16 17:40:17 回复(0)
/*
贪心算法,每次选择***服务器能访问的最大深度,转换次数加一,下次迭代从最大深度开始
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
//    freopen("input.txt","r",stdin);
    vector<string> nn,mm;
    vector<string>::iterator it,index,start,max;
    int n,m; 
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            string s;cin>>s;
            nn.push_back(s);
        }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
       {
           string s;cin >> s;
           mm.push_back(s);
       }
       max = start = mm.begin();
    int res = 0,flag = 0;
    while(res<=m)
    {
        for(int i=0;i<n;i++)
        {
            index=find(start,mm.end(),nn[i]);
            if(index==mm.end())
            {
                cout << res << endl;
                flag = 1;
                break;
            }
             if(max<index)
                 max = index;
        }
        if(index==mm.end())
            break;
        start = max;
        res++;
    }
    if(flag==0)
    cout << -1 << endl;
    flag = 0;
    }
    
    return 0;
}


发表于 2018-04-19 22:44:15 回复(0)

这道题花了好多时间,来看大家讨论才发现自己之前把题目理解错了,一开始以为***服务器每个只能使用一次的,所以觉得贪心好像不太对.如果***服务器可以重复使用的话,贪心就是对的咯,因为假设x1,x2,...xn这个访问序列是最优的(n最小)且y1放在第一个访问可以pass掉的服务器比x1多,那么用y1代替掉x1后,会比x1pass掉更多的服务器,所以结果至少不会差.

include <iostream>

include <string>

include <vector>

include <map>

include <queue>

include <stack>

include <algorithm>

include <cstdio>

include <cstring>

include <cstdlib>

include <cmath>

using namespace std;

int n, m;

void solve_04 ( vector<string> & pxy, vector<string> & ser )
{
int i, j = 0, k = 0, ans = 0;
while ( true )
{
int t = k;
for ( i = 0; i < pxy.size ( ); i ++ )
{
j = t;
while ( j < m && pxy[i] != ser[j] ) j ++;
if ( j == m )
{
cout << ans << endl;
return ;
}
k = max ( k, j );
}
ans ++;
///如果某轮循环k没有前进,说明只有一个***服务器,且服务器中也有它
if ( t == k )
{
cout << -1 << endl;
return ;
}
}
return ;
}

int main ( )
{
while ( cin >> n )
{
int i;
vector< string > pxy( n, "" );
for ( i = 0; i < n; i ++ )
cin >> pxy[i];
cin >> m;
vector< string > ser( m, "" );
for ( i = 0; i < m; i ++ )
cin >> ser[i];
solve_04 ( pxy, ser );
}
return 0;
}

发表于 2018-02-24 19:02:40 回复(0)
#include<stdio.h>
int main(){
    int n,m;
    char dot;//用来接收输入中的字符(小数点和换行符)
    int seq[5000];//用来存储访问服务器中与***服务器IP相同的序列;
    //如:第一个被访问的服务器与第三个***服务器IP相同则seq[0]=2;
    while(scanf("%d",&n)!=EOF){
        //为***服务器赋值
        int s=0;
        int (*daili)[4]=new int[n][4];
        for(int i=0;i<n;i++){
            for(int j=0;j<4;j++){
                scanf("%d",&daili[i][j]);
                scanf("%c",&dot);
            }
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
             int *temp=new int[4];
             //为访问服务器赋值
            for(int j=0;j<4;j++){
                scanf("%d",&temp[j]);
                scanf("%c",&dot);
            }
            for(int k=0;k<n;k++){
                int d=0;
                while(d<4){
                    if(temp[d]==daili[k][d]){
                        d++;
                    }
                    else break;
                }
                if(d==4){//找到第k个***服务器与访问服务器IP相同
                    seq[s++]=k;
                    break;
                }
            }
        }
        for(int i=0;i<s;i++){
            printf("%d ",seq[i]);
        }
        /*
        失败的情况:只有一个***服务器且访问序列中有与该***IP冲突的服务器
        */
        if(n==1){
            for(int i=0;i<s;i++){
                if(seq[i]==0){
                    printf("%d\n",-1);
                    return 0;
                }
            }
        }
        int *server=new int[n];
        for(int j=0;j<n;j++){
                server[j]=0;
        }
        int change=0;//用来记录切换服务器的次数
        int _count=0;
        for(int i=0;i<s;i++){
            int y=seq[i];
            if(server[y]==0){
                server[y]=1;
                _count++;
            }
            if(_count==n){//当前i个访问服务器的IP与所有***服务器的IP冲突,则必存在一次切换***服务器操作
                change++;
                _count=0;
                i--;
                for(int j=0;j<n;j++){
                    server[j]=0;
                }
            }
        }
        printf("%d\n",change);
    }
    return 0;
}

发表于 2018-01-18 11:10:17 回复(0)
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 5000
#define MAX_IP 1000
#define IP_LENGTH 16
int main(int argc, char *argv[])
{
    int N,M,i = 0,j = 0,s = 0;
    char proxy_ip[MAX_IP][IP_LENGTH],server_ip[MAX_SIZE][IP_LENGTH];
    int proxy_sign[MAX_IP] = {0},server_sign[MAX_SIZE] = {-1};
    while(scanf("%d",&N) != EOF)
    {
        s = 0;
        for(i = 0;i < N;i++)
        {
            scanf("%s",proxy_ip[i]);proxy_sign[i] = MAX_SIZE;
        }
        scanf("%d",&M);
        for(i = 0;i < M;i++)
        {
            scanf("%s",server_ip[i]);server_sign[i] = -1;
            for(j = 0;j < N;j++)
                if(server_ip[i][0] == proxy_ip[j][0] && server_ip[i][1] == proxy_ip[j][1] 
                    && strcmp(server_ip[i],proxy_ip[j]) == 0)
                {
                    if(N == 1)
                        s = 1;
                    proxy_sign[j] = proxy_sign[j] > i ? i : proxy_sign[j];
                    server_sign[i] = j;break;    
                }
        }
        int flag = 0,count = -1,k = 0,max_site = 0;
        while(flag == 0 && s == 0)
        {
            flag = 1;max_site = proxy_sign[0];
            for(i = 1;i < N;i++)
            {
                if(max_site < proxy_sign[i])
                    max_site = proxy_sign[i];
                if(max_site == MAX_SIZE)
                    break;
            }
            int p = max_site;
            for(k = 0;k < N;k++)
            {
                for(j = p;j < M;j++)
                    if(server_sign[j] == k)
                    {
                        proxy_sign[k] = j; break;
                    }
                if(j == M)
                    proxy_sign[k] = MAX_SIZE;
            }
            if(max_site != MAX_SIZE)
                flag = 0;
            count++;
            //for(i = 0;i < N;i++)
            //    printf("%d ",proxy_sign[i]);
            //printf("\n");
        }
        printf("%d\n",count);
    }
    return 0;
}
发表于 2018-01-15 19:55:04 回复(0)