双端队列之单调队列——基本数据结构

看到题目我们可以从题目中获取部分关键信息，首先它时要求给定的区域时最小的，其次又是区间最优，通过最优我们可以想到单调性，切记:我们这里的单调条件就是:名画种类递增!

废话不多说，贴上代码：

#include <iostream>
#include <deque>

using namespace std;

const int N = 1e6+100;
const int M = 2010;
int b[N],cnt,a[N],m,n,ansl = 1e8,ansr = 1e8,ans = 1e8;
deque<int> q;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> a[i];
    for(int i = 1; i <= n; i ++ )
    {
        if(! b[a[i]])
            cnt ++ ;
        q.push_back(i);
        b[a[i]] ++ ;
        
        while(b[a[q.front()]] >= 2)
        {
            b[a[q.front()]] -- ;
            q.pop_front();
        }
        if(cnt >= m && q.back() - q.front() + 1 < ans )
            {
                ansl = q.front();
                ansr = q.back();
                ans = ansr -ansl + 1;
            }
    }
    cout << ansl << " " << ansr << endl;
    
    
    return 0;
}

对于stl的使用要特别小心也要熟悉使用，题目中数据N的范围是小于1e6的这个数据范围会把O（n方）的复杂度卡掉，所以要参考nlogn或者是n的复杂度，也要明白这个数据范围出现的时候，标志着这道题目某种程度上要使用数据结构来进行优化算法！！

我们一直在努力！

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/Chenxiaoyu99/article/details/89247022
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:22:14
阅读 ( 1340 )
分类：

双端队列之单调队列——基本数据结构

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看