NC20863 数糖纸(桶排序)

题目

可能很多人要吐槽为什么标题不是“救救blabla”了。
怪人PM6喜欢数糖纸，不同的糖纸有不同的颜色，一共有 N 张糖纸，第 i 张糖纸颜色为 Ci ，它们的位置都是固定的。PM6喜欢五彩缤纷的糖纸，所以他不希望有重复的颜色。他有一次机会，可以收集任意一段连续区间内的糖纸。求出PM6最多能收集多少张糖纸。

输入描述

第一行一个正整数 N ，表示共有 N 张糖纸。
第二行共有 N 个正整数，第 i 个正整数表示第 i 张糖纸的颜色 Ci
对于20%的数据：1<=N<=100
对于40%的数据：1<=N<=1000
对于100%的数据：1<=N<=1e6，0<=Ci<=1e9

输出描述

一个整数表示PM6最多能收集多少张糖纸。

题目分析

1.桶排序的基础想法，可参考 本篇博客
2.题意可直观的理解为，遍历数组一次，找到其中数字不重复的最长区间，
但考虑到 0<=Ci<=1e9 ，如果开辟一个长度为1e9的数组作，似乎不太合理的，
可考虑将其进行离散化，来缩小需开辟数组的长度。

for (int i = 1;i <= n;i ++){
    cin >> a[i];
    b[i] = a[i];
}
sort(b + 1,b + n + 1);
int len = unique(b + 1,b + n + 1) - b - 1;
///离散化
for (int i = 1;i <= n;i ++){
    //离散化后a[i]中存放的是，原a[i]的值在排序后b[i]中的位置
    a[i] = lower_bound(b + 1, b + len + 1,a[i]) - b;
}

3.离散化后，从原来判断某个数是否重复出现，变为判断某个数排序后的位置是否重复出现，
这里通过一个 vis 数组来维护病判断是否重复出现。
4.AC代码

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

const int maxn = 1e6 + 5;
int a[maxn] , b[maxn];
int vis[maxn];
int n;

int main(){
    while (~scanf("%d",&n)){
        for (int i = 1;i <= n;i ++){
            cin >> a[i];
            b[i] = a[i];
        }
        sort(b + 1,b + n + 1);
        int len = unique(b + 1,b + n + 1) - b - 1;
        ///离散化的目的：由于题目中给出的ci的值是1e9,开辟这么大的数组需要很大的空间
        for (int i = 1;i <= n;i ++){
            a[i] = lower_bound(b + 1, b + len + 1,a[i]) - b;///离散化
        }
        for (int i = 0;i <= len ;i ++) vis[i] = 0;
        int l = 1,r = 1;
        int ans = 0;
        while (l <= r && r <= n){
            while (!vis[a[r]] && r <= n){
                vis[a[r]] = 1;
                r ++;
            }
            ans = max(ans,r - l);
            //这里需要注意，因为舒适重复的，获取区间长度后，需要将其遍历过的归零
            while (vis[a[r]]){
                vis[a[l ++]] = 0;
            }
        }
        cout << ans << endl;
    }
    return 0;
}