阿里 笔试 4.3 第一题
这里发下两种不同的解法，一种是set+二分，另一种是排序加单调栈。
个人对拍觉得OK。
第一种
#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;
} 
