P3029

Stevehim · 2023-01-26 23:06:14 · 个人记录

感觉不像蓝题的难度，双指针+离散化一下子就过了然后离散化还不用去重等等等

需要注意的是用x当下标需要用map存储此处，为什么？问就是3次8分得出来的惨痛教训

对了还得注意ans值不能开小了，问就是一次76的教训

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

struct cow {
    int id;
    long long x;
} a[maxn];
int btop;
int ctop;
int idnum;
cow b[maxn];
map<int, bool> m;
map<int, int>m1; //记录次数（不能用数组woq）
int n;
long long ans = 1e17;

bool cmp(cow a, cow b) {
    return a.x < b.x;
}
int cur1;
int cur2;

int main() {
//  freopen("P3029_2.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].id;
        b[++btop] = a[i];
        if (!m[a[i].id]) {
            m[a[i].id] = true;
            idnum++;
        }
    }
    sort(b + 1, b + 1 + n, cmp);
    cur1 = 1;
    cur2 = 1;
    ctop = 1;
    m1[b[1].id]++;
    while (cur1 <= cur2 && cur2 <= n) {
        if (ctop >= idnum) {
            m1[b[cur1].id]--;
            if (!m1[b[cur1].id]) {
                ctop--;
            }
            ans = min(b[cur2].x - b[cur1].x, ans);
            cur1++;
        } else {
            cur2++;
            if (!m1[b[cur2].id]) {
                ctop++;
            }
            m1[b[cur2].id]++;
        }
    }
    cout << ans;
    return 0;
}