首页 > 试题广场 >

彩色袜子

[编程题]彩色袜子

热度指数：44 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛在衣柜里拿出了他的袜子，他把这些袜子摆成一排，一共有 $\mathit n$ 只袜子，袜子总共有 $\mathit m$ 种颜色，颜色编号从 $\mathit 1$ 到 $\mathit m$ 。
现在牛妹想要牛牛找到最小的整数 $\mathit x$ ，使得有一种颜色的袜子出现在任意连续的 $\mathit x$ 个袜子中。如果有多种颜色，牛妹希望找到编号最小的那种颜色。

输入描述:

第一行两个数字和表示袜子的个数和颜色的个数。
第二行有个数字，第个数字表示第个袜子的颜色是。

输出描述:

一行两个数字表示答案。
第一个数字为最小的长度，第二个数字为颜色编号最小的编号。

示例1

输入

2 2
1 2

输出

2 1

示例2

输入

4 2
1 2 1 2

输出

2 1

说明

当时，满足的区间只有一个，此时同时出现在这些区间里面的袜子颜色为和。
当时，满足的区间为和，此时同时出现在这些区间里面的袜子颜色为和。
当时，满足的区间为、和，此时同时出现在这些区间里面的袜子颜色为和。
当时，满足的区间为、、和，此时没有同时出现在这些区间里面的袜子颜色。

算法知识视频讲解

C/C++

shadox

#include <bits/stdc++.h>
using namespace std;

int f[1000005], g[1000005];
set<int>s;
int main(){
    int n, m, x = 1e9;
    cin >> n >> m;
    s.clear();
    memset(f, -1, sizeof(f));
    memset(g, 0, sizeof(g));
    for(int i = 0; i < n; i++){
        int c;
        cin >> c;
        g[c] = max(g[c], i - f[c]);
        f[c] = i;
        s.insert(c);
    }
    for(auto it : s){
        g[it] = max(g[it], n - f[it]);
    }
    int ans = 0;
    for(auto it : s){
        if(x > g[it]){
            x = g[it];
            ans = it;
        }
    }
    cout << x << ' ' << ans << endl;
}

编辑于 2021-03-18 22:35:00 回复(0)