CF1848B Vika and the Bridge 题解

题目大意

~~给个题目传送门吧，感觉题意已经很清楚了~~

题目传送门

分析

（~~我不会告诉你我第一眼看过去是二分~~）

因为我们只能改一块木板的颜色，所以可以考虑贪心。大概算了下复杂度，也没有问题。

题解

我们要去求每种颜色最大距离的最小值，那我们可以先去求每种颜色的最大值。

求完以后，直接将每种颜色的最大值减半，就是我们的最远距离 \(\dots\) 了吗？

并不是，因为有可能最大值减半后，这个新的值比原来的次大值小，那么最远距离就成了次大值。所以我们一开始也要求出每种颜色的次大值。最后将每种颜色最大值的一半与次大值取较大的一个，也就是这个颜色的最远距离，再取所有颜色的最远距离的最小值，就是答案啦。

~~好多最值，自己差点绕进去 qwq~~

时间复杂度： \(O(n + m)\)

代码

#include <bits/stdc++.h>
#define M 200005

using namespace std;

int T, m, n, c[M], maxn[M], pre[M], ci_maxn[M], ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T;
    for(int t = 1; t <= T; ++ t) {
        ans = INT_MAX;
        cin >> n >> m;
        for(int i = 1; i <= m; ++ i)    
            pre[i] = maxn[i] = ci_maxn[i] = 0;
        for(int i = 1; i <= n; ++ i) {
            cin >> c[i];
            if(i - pre[c[i]] - 1 > maxn[c[i]]) {
                ci_maxn[c[i]] = maxn[c[i]];
                maxn[c[i]] = i - pre[c[i]] - 1;
            }
            else
                if(i - pre[c[i]] - 1 > ci_maxn[c[i]])
                    ci_maxn[c[i]] = i - pre[c[i]] - 1;
            pre[c[i]] = i;
        }
        for(int i = 1; i <= m; ++ i) {
            if(n - pre[i] > maxn[i]) {
                ci_maxn[i] = maxn[i];
                maxn[i] = n - pre[i];
            }
            else
                if(n - pre[i] > ci_maxn[i])
                    ci_maxn[i] = n - pre[i];
            ans = min(max(maxn[i] / 2, ci_maxn[i]), ans);
        }
        cout << ans << '\n';
    }
}