首页 > 代码库 > zoj3633

zoj3633

ZOj 3633

点击打开链接

大致题意:

给你n个数,m个查询,每个查询给出俩个数a,b,查询从b->a(从右到左)有没有重复出现的数,有的话输出第一个出现的重复的数,否则输出OK;

解题思路:

我是直接用map查询时,从后往前,map的find()判断是否有重复。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define PI acos(-1.0)
#define eps 1e-8
#define LL long long
#define moo 1000000007
#define INF -999999999
using namespace std;
int num[510000];
map<int,int> ant;
int n,m,u,v;
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&u,&v);
            ant.clear();
            int i;
            for(i=v;i>=u;i--)
            {
                if(!ant.count(num[i]))
                    ant[num[i]]=1;
                else
                {
                   break;
                }
            }
            if(i<u)
                printf("OK\n");
            else
                printf("%d\n",num[i]);
        }
        printf("\n");
    }
    return 0;
}



zoj3633