身高最接近的牛

AisDaeun 13 2023-12-02

红黑树解法

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    set<pair<int, int>> st;
    st.emplace(x, 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);
        st.emplace(x, i);
        auto p = st.find({x, i});
        auto a = prev(p), b = next(p);
        tuple<int, int, int> res {INT_MAX, INT_MAX, INT_MAX};
        if (a != st.end()) res = min(res, {x - a->first, a->first, a->second});
        if (b != st.end()) res = min(res, {b->first - x, b->first, b->second});
        printf("%d %d\n", get<0>(res), get<2>(res));
    }
}

链表

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    set<pair<int, int>> st;
    st.emplace(x, 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);
        st.emplace(x, i);
        auto p = st.find({x, i});
        auto a = prev(p), b = next(p);
        tuple<int, int, int> res {INT_MAX, INT_MAX, INT_MAX};
        if (a != st.end()) res = min(res, {x - a->first, a->first, a->second});
        if (b != st.end()) res = min(res, {b->first - x, b->first, b->second});
        printf("%d %d\n", get<0>(res), get<2>(res));
    }
}