cf1208B B. Uniqueness（1500）

傷城~ 2024-04-18 14:23 72阅读 0赞

该题要逆向思维， 不看删除的， 要看保留的。  
[讲解][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 2e3+50;
    const int inf = 0x3f3f3f3f;
    int a[maxn];
    
    map<int, int>p;
    
    set<int>book2;
    int main()
    { 
        ios_base::sync_with_stdio(false);
        int n;
        cin>>n;
        for(int i = 1;i <= n;i++)
        { 
            cin>>a[i];
        }
    
        int ans = inf;// 初始化答案
        int l = 1;
        p.clear();
        book2.clear();
        ans = 333333;
        while(l <= n)
        { 
            if(p[a[l]])
            { 
                break;
            }
            else p[a[l]] = l;
            l++;
        }
        l--;//左面保留部分的上限
        ans = n-l;
        int r = n;
        while(r >= 1)
        { 
            if(book2.count(a[r]))// 如果该数在右半边出现过，且肯定没在左半边出现过
            { 
                ans = min(ans, r-l);//取小 结束
                break;
            }
            else book2.insert(a[r]);// 否则标记一下该数
    
            if(p[a[r]] && l >= p[a[r]])// 如果左右出现重复的， 去掉左面的
            { 
                
                ans = min(ans, r-l);
                l = p[a[r]] -1;
            }
            r--;
        }
        cout<<ans;
    
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/dream_it_/article/details/100078848

发表评论取消回复

表情：

评论列表（有 0 条评论，72人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1217B

CF1217B 题意： > 有一个有 $ x $ 个头的龙，你有 $ n $ 种方案，每种方案中包含你可以砍掉的头 $ d\_i $ 和龙会生长的头 $ h...

悠悠/ 2024年04月20日 10:34/ 0 赞/ 64 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 78 阅读

相关 CF1200B

CF1200B 解法： > 贪心。当在第i列时，尽可能多的取走第i列的木块使得袋子里的木块尽可能多 CODE: include<iostre...

本是古典何须时尚/ 2024年04月20日 10:29/ 0 赞/ 64 阅读

相关 CF1197B

CF1197B 题意： > 出n个柱子，每个柱子一个圆盘，其半径各不相同，每次只能将柱子上只有一个圆盘的移到相邻位置，问能否全部移到一个柱子上。解法：...

落日映苍穹つ/ 2024年04月20日 10:28/ 0 赞/ 82 阅读

相关 CF1207B

CF1207B-Square Filling 题意： > 两个矩阵a,b，已知矩阵b，每次能修改b矩阵中相邻的四个格（b为空矩阵），使b变为a 解法： ...

梦里梦外;/ 2024年04月20日 10:28/ 0 赞/ 52 阅读

相关 CF1195B

CF1195B 题意： > 有一个盒子，每次可以做两个操作： > > > 1.每次吃掉一块蛋糕 > > 2.每次放入比上一次放入数多1的蛋糕 > ...

墨蓝/ 2024年04月20日 10:28/ 0 赞/ 65 阅读

相关 CF1208B

CF1208B 题意： > 给出n个数字，找出最小的一端连续区间进行删除操作，使其剩余元素不含重复元素，求要删除的最小区间长度解法： > 删除子段...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:28/ 0 赞/ 61 阅读

相关 CF1204B

CF1204B-Mislove Has Lost an Array 题意： > 给你n，l，r 表示在区间1-n内至少有l个不相同的数至多有r个不相同的数，...

女爷i/ 2024年04月20日 10:26/ 0 赞/ 65 阅读

相关 cf1208B B. Uniqueness（1500）

题要逆向思维，不看删除的，要看保留的。 [讲解][Link 1] include<bits/stdc++.h> using namespace ...

傷城~/ 2024年04月18日 14:23/ 0 赞/ 73 阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 77 阅读