C++题解：蜗牛旅行

89 阅读 0 评论 59 点赞

我是靠谱客的博主怕黑高山，最近开发中收集的这篇文章主要介绍C++题解：蜗牛旅行，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

题解

题目

1000ms
524288K

蜗牛在制定今天的旅游计划，有 nn 个景点可选，它已经把这些景点按照顺路游览的顺序排成一排了，每个地方有相应的景观，这里用一个整数表示。

蜗牛希望选取连续的一段景点，还要选出来的每一个景点的景观都不同，问它最多能选出多少个景点进行旅游。

输入格式

第一行，一个正整数 n(1≤n≤10^5)。

第二行，包含 n 个正整数 ai(1≤ai≤10^6) ，第 i 个整数表示第 i 个景点的景观。

输出格式

输出一行，包含一个整数，表示蜗牛最多能选出的景点数。

数据范围

对于 60% 的数据，1≤n≤10^3

对于 100% 的数据，1≤n≤10^5,1≤ai≤10^6

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 tour.in，输出文件为 tour.out

样例输入
5
1 2 3 2 1
样例输出
3

题解：

知识点：队列

分析：模拟一遍即可，注意细节

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
const int N=1e6+5;
queue<int> q;
map<int,int> a;//用map节省空间
bool vis[N];
int main(){
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    int n,ans=0;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        int a1;
        scanf("%d",&a1);
        a[i]=a1;
    }
    for (int i=0;i<n;i++){
        if (!vis[a[i]]){
            q.push(a[i]);
            vis[a[i]]=true;
        }else{
            while (!q.empty()){
                if (q.front()!=a[i]){
                    vis[q.front()]=false;
                    q.pop();
                }else{
                    q.pop();
                    vis[q.front()]=false;
                    q.push(a[i]);
                    break;
                }
            }
        }
        if (q.size()>ans){//注意，不能用max
            ans=q.size();
        }
    }
    cout<<ans<<endl;
    return 0;
}