阿里 笔试 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; }