acwing 651. 逛画展-白红宇

acwing 651. 逛画展

阅读量：4599 次

发布时间：2019-06-09

本文共 2474 字，大约阅读时间需要 8 分钟。

地址

博览馆正在展出由世上最佳的 M 位画家所画的图画。

wangjy想到博览馆去看这几位大师的作品。

可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，a和b，代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画，而门票的价钱就是一张图画一元。

为了看到更多名师的画，wangjy希望入场后可以看到所有名师的图画(至少各一张)。

可是他又想节省金钱。。。

作为wangjy的朋友，他请你写一个程序决定他购买门票时的 a 值和 b 值。

输入格式

第一行包含两个整数 N 和 M，表示图画总数和画家数量。

第二行包含 N 个整数，它们都介于 1 和 M 之间，代表画作作者的编号。

输出格式

输出两个整数 a 和 b。

数据保证有解，如果存在多个解，则输出 a 最小的那个解。

数据范围

输入样例：

12 52 5 3 1 3 2 4 1 1 5 4 3

输出样例：

2 7

主要是考虑使用滑动窗口使用哈希记录其中各个画家出现的次数但是tle

#include 
      
       #include 
       using namespace std;const int N = 1e6+10;int huaArr[N];map
        
          mapm;int n ,m;int cnt = 0;int ans = 1e9;int ansa = 1e9;int ansb = 1e9;int main(){     ios::sync_with_stdio(false);    cin >> n >> m;    for(int i =1;i<= n;i++){        cin >> huaArr[i];    }        int l = 1; int r= 0;        for(int i =1;i <=n;i++){        //i 幅画放去l r 区间        if (mapm[huaArr[i]] == 0)//曾经没有出现过            cnt++;        r++;        mapm[huaArr[i]]++;                //开始进行缩减        while(mapm[huaArr[l]] >=2){            //该副画 排除区间            mapm[huaArr[l]]--;            l++;        }                if(cnt >= m && r-l+1 < ans){            ans = r-l+1;            ansa = l;            ansb = r;        }    }        cout << ansa << " " << ansb << endl;            return 0;}

tle

后面参考其他同学的代码（）

把自己的map改成了vector 过了。这也是 oj与leetcode的区别吧

1 #include 
      
        2 #include 
        3 #include 
        
          4 using namespace std; 5  6 const int N = 1e6+10; 7  8 vector
         
           huaArr(N,0); 9 10 vector
          
            v(N,0);11 int n ,m;12 13 int cnt = 0;14 15 int ans = 1e9;16 int ansa = 1e9;17 int ansb = 1e9;18 19 20 int main()21 {22      ios::sync_with_stdio(false);23     cin >> n >> m;24     for(int i =1;i<= n;i++){25         cin >> huaArr[i];26     }27     28     int l = 1; int r= 0;29     30     for(int i =1;i <=n;i++){31         //i 幅画放去l r 区间32         if (v[huaArr[i]] == 0)//曾经没有出现过33             cnt++;34         r++;35         v[huaArr[i]]++;36         37         //开始进行缩减38         while(v[huaArr[l]] >=2){39             //该副画 排除区间40             v[huaArr[l]]--;41             l++;42         }43         44         if(cnt >= m && r-l+1 < ans){45             ans = r-l+1;46             ansa = l;47             ansb = r;48         }49     }50     51     cout << ansa << " " << ansb << endl;52     53     54     return 0;55 }

转载于:https://www.cnblogs.com/itdef/p/10858238.html

你可能感兴趣的文章