代理伺服器-貪心算法

上文連結：https://blog.csdn.net/slient_love/article/details/104311852

代理伺服器-貪心算法

題目描述

使用代理伺服器能夠在一定程度上隐藏用戶端資訊，進而保護使用者在網際網路上的隐私。我們知道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。

示例：

輸入：

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

輸出：

做題思路：

此題用貪心算法比較好解。由題意可知，隻有當N=1時，且代理伺服器的IP位址在伺服器IP位址隊列中時，輸出才為“-1”。

代碼展示：

#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;

//每次調用，在目标串中找最長可以通路到的結點，從該結點開始再往後找最長
int solve(char a[1000][16],int n,char b[5000][16],int m)
{
    int i,j;
    int max=-1;//max為該代理伺服器可以通路的最多個數-1
    //雙層for循環用來判斷該代理伺服器是否可以通路完所有的伺服器，若不能則得出可以通路到的最長節點
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(!strcmp(a[i],b[j])){//相等
                if(max<j)
                    max=j;
                break;
            }
        }
        if(j == m)
            return 0;
    }
    //該種情況表示隻有一個代理伺服器，并且該代理伺服器的IP位址與伺服器的IP位址有一樣的
    if(n==1&&max!=-1)
        return -1;
    //切換一次代理伺服器位址
    return 1+solve(a,n,b+max,m-max);
}

int main()
{
    int n,m;
    while(cin>>n){
        char a[n][16];
        for(int i = 0;i <n ;i++)
            cin>>a[i];
        cin>>m;
        char b[m][16];
        for(int i = 0;i <m ;i++)
            cin>>b[i];
        cout<<solve(a,n,b,m);
    }
    return 0;
}

strcmp函數：

頭檔案： string.h

strcmp(const char *s1,const char * s2)

規則

當s1<s2時，傳回為負數;

當s1==s2時，傳回值= 0;

當s1>s2時，傳回正數。

特别注意:strcmp(const char *s1,const char * s2)這裡面隻能比較字元串，即可用于比較兩個字元串常量，或比較數組和字元串常量，不能比較數字等其他形式的參數。

代理伺服器-貪心算法