阿里 笔试 4.3 第一题

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;

// a为有价值的数，
// 当且仅当左侧存在大于a的数，取最小大于a的数为f
// 当且仅当右侧存在小于a的数，取最大小于a的数为g
// 要求f为g的倍数

// 还是回归了考试时最初的思路，用二叉搜索树
// 当时紧张忘了可以用自带的二分

const int MAXN = 10000 + 5;
const int MAXM = 14;

int n;
int a[MAXN];
int lf[MAXN]; // lf[i[表示a[i]左侧大于它的数的最小值
int rt[MAXN]; // rt[i[表示a[i]右侧小于它的数的最大值

set<int> s;
set<int>::iterator it;

int main()
{
    freopen("in_1.txt", "r", stdin);
    cin >> n;
    if (n < 3)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        // 返回的是第一个比a[i]大的迭代器
        it = s.upper_bound(a[i]);
        if (it != s.end())
            lf[i] = *it;
        s.insert(a[i]);
    }
    s.clear();
    for (int i = n; i >= 1; --i)
    {
        it = s.upper_bound(-a[i]);
        if (it != s.end())
            rt[i] = -(*it);
        s.insert(-a[i]);
    }
    int ans = 0;
    for (int i = 2; i < n; ++i)
    {
        if (lf[i] != 0 && rt[i] != 0)
        {
            if (lf[i] % rt[i] == 0)
                ans++;
        }
    }
    cout << ans << endl;
    fclose(stdin);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;

// a为有价值的数，
// 当且仅当左侧存在大于a的数，取最小大于a的数为f
// 当且仅当右侧存在小于a的数，取最大小于a的数为g
// 要求f为g的倍数

// 暴力的话，就是遍历每一个a，查找其f和g，看是否满足条件
// 这样复杂度为O(n^2)

// 可以考虑在查找f和g上优化，如果使用二叉搜索树去，比如SET
// 直接排序算了，我想啥呢

struct num
{
    int val;
    int index;
};

bool cmp(num x, num y)
{
    return x.val < y.val;
}

const int MAXN = 10000 + 5;
const int MAXM = 14;
int n;
num a[MAXN];
stack<num> s;
int lf[MAXN]; // lf[i[表示a[i]左侧大于它的数的最小值
int rt[MAXN]; // rt[i[表示a[i]右侧小于它的数的最大值
// #define DEBUG

int main()
{
    freopen("in_1.txt", "r", stdin);
    cin >> n;
    if (n < 3)
    {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].val;
        a[i].index = i;
    }

    stable_sort(a + 1, a + 1 + n, cmp);

#ifdef DEBUG
    for (int i = 1; i <= n; ++i)
    {
        cout << a[i].index << ' ' << a[i].val << endl;
    }
#endif

    memset(lf, -1, sizeof(lf));
    memset(rt, -1, sizeof(rt));

    for (int i = 1; i <= n; ++i)
    {
        if (s.empty())
        {
            s.push(a[i]);
        }
        else if (s.top().index > a[i].index)
        {
            rt[i] = s.top().val;
            s.push(a[i]);
        }
        else
        {
            while (!s.empty() && s.top().index < a[i].index)
                s.pop();
            if (!s.empty())
                rt[i] = s.top().val;
            s.push(a[i]);
        }
    }

    while (!s.empty())
        s.pop();

    for (int i = n; i >= 1; --i)
    {
        if (s.empty())
        {
            s.push(a[i]);
        }
        else if (s.top().index < a[i].index)
        {
            lf[i] = s.top().val;
            s.push(a[i]);
        }
        else
        {
            while (!s.empty() && s.top().index > a[i].index)
                s.pop();
            if (!s.empty())
                lf[i] = s.top().val;
            s.push(a[i]);
        }
    }

#ifdef DEBUG
    for (int i = 1; i <= n; ++i)
        cout << rt[i] << ' ';
    cout << endl;
    for (int i = 1; i <= n; ++i)
        cout << lf[i] << ' ';
    cout << endl;
#endif

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (lf[i] == -1 || rt[i] == -1)
            continue;
        if (lf[i] == 0 || rt[i] == 0)
            continue;
        if (lf[i] % rt[i] == 0)
            ++ans;
    }
    cout << ans << endl;

    fclose(stdin);
    return 0;
}