codeforcesB. Amr and The Large Array

￡神魔★判官ぃ 2022-08-02 07:29 134阅读 0赞

B. Amr and The Large Array
    time limit per test
    1 second
    memory limit per test
    256 megabytes
    input
    standard input
    output
    standard output
    
    Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.
    
    Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.
    
    Help Amr by choosing the smallest subsegment possible.
    Input
    
    The first line contains one number n (1 ≤ n ≤ 105), the size of the array.
    
    The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.
    Output
    
    Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.
    
    If there are several possible answers you may output any of them.
    Sample test(s)
    Input
    
    5
    1 1 2 2 1
    
    Output
    
    1 5
    
    Input
    
    5
    1 2 2 3 1
    
    Output
    
    2 3
    
    Input
    
    6
    1 2 2 1 1 2
    
    Output
    
    1 5
    
    Note
    
    A subsegment B of an array A from l to r is an array of size r - l + 1 where Bi = Al + i - 1 for all 1 ≤ i ≤ r - l + 1

数组的美丽值是出现次数最多的某些元素的出现次数，求最短的子数组，使他跟原数组美丽值相同。不会就乱写，当时思维比较混乱，WA了好几发，后来看了题解，才明白最优解法。先贴自己写的，在贴看了题解之后写的。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int a[100010];
    map<int,int> mp;
    vector<int> v[1000010];
    int main()
    {
    
        int n=in();
    
        for(int i=0;i<n;i++)
        {
            a[i]=in();
    
            mp[a[i]]++;
        }
        int mx=0;
        set<int> s;
        map<int,int>::iterator  it;
        for(it=mp.begin();it!=mp.end();it++)
        {
            if(it->second>=mx)
            {
                mx=it->second;
    
            }
        }
        for(it=mp.begin();it!=mp.end();it++)
        {
            if(it->second==mx)
            {
                s.insert(it->first);
    
            }
        }
        for(int i=0;i<n;i++)
        {
            if(s.find(a[i])!=s.end())
            {
                v[a[i]].push_back(i);
            }
        }
        set<int>::iterator itt;
        int ans1,ans2;
        int mn=inf;
        for(itt=s.begin();itt!=s.end();itt++)
        {
            int len=v[*itt].size()-1;
            if(v[*itt][len]-v[*itt][0]<mn)
            {
                mn=v[*itt][len]-v[*itt][0];
                ans1=v[*itt][0];
                ans2=v[*itt][len];
            }
        }
        cout<<ans1+1<<" "<<ans2+1;
    
    
        return 0;
    }

l数组记录每个数的第一次出现位置，m数组记录每个数的出现个数。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int m[1000010];
    int l[1000010];
    int main()
    {
    
        int n=in();
        int x,ans1,ans2;
        int mx=0;
        int mn=inf;
        for(int i=0;i<n;i++)
        {
            x=in();
            if(m[x]==0)
            {
                m[x]=1;
                l[x]=i;
            }
            else m[x]++;
            if(m[x]>mx)
            {
                mx=m[x];
                ans1=l[x];
                ans2=i;
                mn=ans2-ans1;
            }
            else if(m[x]==mx && i-l[x]<mn)
            {
                ans1=l[x];
                ans2=i;
                mn=ans2-ans1;
            }
        }
        cout<<ans1+1<<" "<<ans2+1;
    
        return 0;
    }