题解 | #代理服务器#

• 贪心的思路： 借助筛子的比喻，很快迎刃而解

• 切换次数最少 ——> 本次切换选择的Vpn使用的时间尽量长

• 根据访问序列，访问了和n-1个Vpn相同的serve（一直都不会切换）

• 直到最后一个剩余的Vpn也和serve相同必须切换

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string vpn[1001];
string serve[5001];
bool flag[1001];

int choose(int m,int n){//
    int k=n;//可用代理数量
    int sum=0;//切换次数
    memset(flag,0,sizeof(flag));
    for(int i=0;i<m;i++){//从头遍历访问服务器
        for(int j=0;j<n;j++){//比较当前服务器和代理是否相同
            if(serve[i]==vpn[j]&&flag[j]==false){//第一次相同
                flag[j]=true;//标记对应代理为不可用
                k--;
                break;
                }
            }
        
        if(k==0){//当前访问将导致无可用代理
            if(n==1)return -1;//只有一个代理则失败
            memset(flag,0,sizeof(flag));//重置可用代理数量及标记
            k=n;
            sum++;
            i--;//回退一次
         }
        }
    return sum;
}

int main(){
    int n,m;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)cin>>vpn[i];
        scanf("%d",&m);
        for(int i=0;i<m;i++)cin>>serve[i];
        printf("%d\n",choose(m,n));
        
    }
    return 0;
}

ps：自己做的时候盯着前n-1个Vpn被访问了，切换的时间又单独考虑很麻烦

• 关键抓住切换的时机，全都被标记了才切换，切换时可以回退一次，使状态和开始完全相同