cf1208B B. Uniqueness（1500）

傷城~ 2024-04-18 14:23 93阅读 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 条评论，93人围观）

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

相关阅读

相关 CF1214B

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

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

相关 CF1208C

CF1208C > 这场杜老师大战tourist的比赛怎么这么多人类智慧题。。。题意： > 构造一个 $ n \\times n $ 的矩阵，使得该矩阵...

迈不过友情╰/ 2024年04月20日 10:31/ 0 赞/ 100 阅读

相关 CF1208A

CF1208A 题意： > 就是把斐波那契数列的+改成异或，求第n项的值。解法： > 又是一个人类智慧题，打表找规律。 > 可以发现答案在 $...

雨点打透心脏的1/2处/ 2024年04月20日 10:30/ 0 赞/ 92 阅读

相关 CF1200B

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

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

相关 CF1207B

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

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

相关 CF1208B

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

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

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 97 阅读

相关 cf1208B B. Uniqueness（1500）

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

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

相关【反悔贪心】CF1278B CF11B

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

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

相关 CodeForces1208A&B

CodeForces1208A 不得不承认,这题猛地一看吓到我了,吓得我直接看了\\(B\\)题,要不是\\(B\\)也吓到我了我就直接做\\(B\\)了. 打打表,找

女爷i/ 2023年06月02日 11:56/ 0 赞/ 12 阅读