首页 > 试题广场 >

代理服务器

[编程题]代理服务器

热度指数：33982 时间限制：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

输出

算法知识视频讲解

牛客729154675号

#include <stdbool.h>
#include <stdio.h>

//想象成你有n种武器去面对m个敌人，每种武器刚好都有一种有对应抗性的敌人，需要换武器应对
//尽量少换武器那当然是，选一个一路打，打得越多越好
//因此从前往后遍历，直到遇到过所有种类抗性的敌人为止，算一个轮回，因为之前的怪物都可以用最后遇到的敌人对应的武器来砍翻。
//O(nm)的复杂度，因为每个怪都要遍历一次武器，看对应哪一把。
//但凡我有两把武器，都不可能打不过，输出-1；因此只有在只有一把武器，且刚好有抗性敌人的时候会失败，输出-1

int main() {
    int n, m;
    while (scanf("%d", &n) != EOF) {
        char procyIP[n][16], temp[16];
        bool used[n],flag=false;
        int used_count = 0, change_count = 0;
        for(int i=0; i<n; i++){
            scanf("%s", procyIP[i]);
            used[i] = false;
        }
        scanf("%d", &m);
        if(n!=1){
            for(int i=0; i<m; i++){
                scanf(" %s", temp);
                for(int j=0; j<n; j++){         //逐个比对
                    if(!used[j] && (strcmp(procyIP[j], temp) == 0)){
                        //这把武器没用过，且刚好遇到抗性怪
                        used_count++;
                        if(used_count == n){    //要换武器了
                            change_count++;
                            used_count = 1;
                            for(int k=0; k<n; k++){used[k] = false;}
                        }
                        used[j] = true;
                        break;                  //剩下的代理不用比了，因为两两不相同
                    }
                }
            }
            printf("%d\n", change_count);
        }else{
            for(int i=0; i<m; i++){
                scanf("%s", temp);
                if(!flag && strcmp(procyIP[0], temp) == 0){  //遇到困难就自杀
                    printf("-1\n");
                    flag = true;
                }
            }
            if(!flag){printf("0\n");}               //没遇到就神作
        }
    }
    return 0;
}

发表于 2024-02-26 23:39:35 回复(0)

牛客负010号

#include <stdio.h>

#include <string.h>

int main(){

int n;

while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case

int i,m,j;

char proxy[n][20];

for(i=0;i<n;++i){

scanf("%s",proxy[i]);

}

scanf("%d",&m);

char server[m][20];

for(i=0;i<m;++i){

scanf("%s",server[i]);

}

int index=0,count=0,flag=1;

while(flag&&index<m){

int max=0;

for(i=0;i<n;++i){

int j=index;

while(strcmp(proxy[i],server[j])&&j<m){

++j;

}

if(j-index>max){

max=j-index;

}

if(max==0){

flag=0;

}

count++;

index += max;

}

if(flag){

printf("%d",count-1);

}else{

printf("-1");

}

return 0;

}

发表于 2023-01-01 15:08:05 回复(0)

Trenchy

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
int n,m;
char proxy[1000][18],server[5000][18];
while(scanf("%d",&n)!=EOF){
char label[1000]={'1'};//标记代理服务器可用性
char visit[5000];//标记服务器是否被访问
char *currentIp;//存储当前服务器ip
int c=0;//计数器
for(int i=0;i<n;i++) scanf("%s",proxy[i]);
scanf("%d",&m);
for(int i=0;i<m;i++) scanf("%s",server[i]);
int k=0;//记录最近被淘汰的代理服务器
for(int i=0;i<m;i=i+1){//顺序访问服务器
currentIp = server[i];
for(int j=0;j<n;j++){//贪心式试探代理服务器，找到能访问的最远的那台
if(label[j]!='0'){
if(strcmp(currentIp,proxy[j])==0){
label[j]='0';//淘汰
k=j;//记录最近被淘汰的那台，它可能是目前能访问的最多的那台
}else visit[i]='1';//存在代理服务器以访问服务器
}
}
//printf("%d ",visit[i]-'0');
if(visit[i]!='1'){//表示所有代理服务服务器不可用，重置标记数组,并进行一次切换
if(n==1){//没有可切换的代理服务器
c=-1;
break;
}else{
for(int j=0;j<n;j++)//重置代理服务器标记数组
if(j!=k) label[j]='1';
c++;//切换一次
i=i-1;//回退一次
}
}
}
printf("%d\n",c);
}
}

发表于 2022-01-20 21:33:17 回复(0)