洛谷题单指南-前缀和差分与离散化-P3029 [USACO11NOV] Cow Lineup S

原题链接：https://www.luogu.com.cn/problem/P3029

题意解读：不同的坐标位置有不同种类的牛，要计算一个最小的区间，包括所有种类的牛。

解题思路：

由于坐标位置不连续，并且数值范围较大，因此需要离散化处理，将坐标处理成1~n连续分布

由于种类编号数值范围也比较大，也需要离散化处理，去重后的种类数量记为cnt2

设t[i] = x表示离散化之后，第i个坐标位置是x类型的牛

这样一来，问题简化成：在t[]中，找到一个区间，使得区间内包括cnt2种不同数字，并且区间端点l，r在离散化之前的差值最小，

通过双指针+哈希数组即可解决。

100分代码：

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

const int N = 50005;
int x[N], id[N], t[N], h[N];
int a[N], cnt1, b[N], bb[N], cnt2;
map<int, int> ha, hb;
int n, ans = INT_MAX;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> id[i];
        a[++cnt1] = x[i];
        b[++cnt2] = id[i];
    }
    //对a排序、不用去重,牛不会在同一个位置
    sort(a + 1, a + cnt1 + 1);
    //对b排序、去重
    sort(b + 1, b + cnt2 + 1);
    int j = 0;
    for(int i = 1; i <= cnt2; i++)
    {
        if(i == 1 || b[i] != b[i - 1])
        {
            bb[++j] = b[i];
        }
    }
    cnt2 = j;
    //a离散化
    for(int i = 1; i <= cnt1; i++) ha[a[i]] = i;
    //bb离散化
    for(int i = 1; i <= cnt2; i++) hb[bb[i]] = i;
    //将x替换为离散化后的值
    for(int i = 1; i <= n; i++) x[i] = ha[x[i]];
    //将id替换为离散化后的值
    for(int i = 1; i <= n; i++) id[i] = hb[id[i]];
    //将坐标位置对应的牛种类填入数组t
    for(int i = 1; i <= n; i++) 
    {
        t[x[i]] = id[i];
    }
    //双指针找包含cnt2个不同整数的最小区间
    int l = 1, r = 0, cnt = 0;
    while(l <= n && r <= n)
    {
        while(r <= n && h[t[l]] <= 1)
        {
            h[t[++r]]++;
            if(h[t[r]] == 1) cnt++;
            if(cnt == cnt2) ans = min(ans, a[r] - a[l]);
        }
        while(h[t[l]] > 1)
        {
            h[t[l++]]--;
            if(cnt == cnt2) ans = min(ans, a[r] - a[l]);
        }
    }
    cout << ans;
    return 0;
}