2022-10-28-ht数据库笔试-110min

禁止任何人未经发件人许可以任何形式（包括但不限于部分地泄露、复制或散发）不当地使用本邮件中的信息

3个笔试题，word文件，72小时回复邮件即可，无监考。

// #include <iostream>
// #include <vector>
// #include <stack>
// int main()
// {
//     std::vector<double> v = {13.5, 13.6, 13.4, 13.3, 13.5, 13.9, 13.1, 20.1, 20.2, 20.3};
//     uint32_t n = v.size();
//     std::vector<uint32_t> maxArrLen(n);
//     std::stack<uint32_t> st;
//     for (uint32_t i = 0; i < n; i++)
//     {
//         while (!st.empty() && v[st.top()] <= v[i])
//             st.pop();
//         maxArrLen[i] = st.empty() ? i + 1 : i - st.top();
//         st.push(i);
//     }
//     for (uint32_t i = 0; i < n; i++)
//         std::cout << maxArrLen[i] << " ";
//     return 0;
// }

// #include <iostream>
// #include <cmath>

// int main()
// {
//     unsigned long long M1, M2, m1, m2, t = 0, n;
//     std::cin >> M1 >> M2;
//     m1 = M1;
//     m2 = M2;

//     if (m2 > m1)
//     {
//         unsigned long long out = m2 - m1; // n(1+n)=2out
//         n = (unsigned long long)(std::sqrt(1 + 8 * out) - 1) / 2;
//         unsigned long long c = (1 + n) * n / 2;
//         m2 = m2 - c;
//         t = n + 1;
//         if (c < out && m2 >= n + 1)
//         {
//             m2 = m2 - (n + 1);
//             t++;
//         }
//     }
//     else
//     {
//         unsigned long long out = m1 - m2;
//         n = (unsigned long long)(std::sqrt(1 + 8 * out) - 1) / 2;
//         unsigned long long c = (1 + n) * n / 2;
//         m1 = m1 - c;
//         t = n + 1;
//     }

//     // 接下来轮流地
//     // 从m1上申请t、t+2、t+4...t+2n个字节, t(n+1)+(2+2n)n/2=tn+t+n(1+n)=n*n+(t+1)n+t-m1<=0
//     // 从m2上申请t+1、t+3、t+5...、t+2n-1或t+2n+1个字节
//     if (m1 >= t)
//     {
//         n = (std::sqrt((t + 1) * (t + 1) + 2 * t + 1 + 4 * m1 - 4 * t) - t - 1) / 2;
//         m1 = m1 - (n * n + (t + 1) * n + t);
//         m2 = m2 - (n * n + (t + 1) * n + t + n + 1 - (t + 2 * n + 1)); // Bug：m2是无符号数，不能提前多减一个数再判断是否小于0再加上多减去的数
//         if (m2 >= t + 2 * n + 1)
//         {
//             m2 -= t + 2 * n + 1;
//             t += 2 * n + 2;
//         }
//         else
//             t += 2 * n + 1;
//     }
//     std::cout << "Answer: " << t << ", " << m1 << ", " << m2 << "\n";

//     // 验证程序
//     m1 = M1, m2 = M2, t = 0;
//     while (true)
//     {
//         if (m1 >= t && m2 >= t)
//         {
//             if (m1 < m2)
//                 m2 -= t;
//             else
//                 m1 -= t;
//         }
//         else if (m1 >= t)
//             m1 -= t;
//         else if (m2 >= t)
//             m2 -= t;
//         else
//             break;
//         t++;
//     }
//     std::cout << "GroundTruth: " << t << ", " << m1 << ", " << m2 << "\n";
//     return 0;
// }
// // 1000000000000000000 99999999999999999
// // Answer: 1483239697, 646162599, 717131344
// // GroundTruth: 1483239697, 646162599, 717131344

// // 只有一些if判断、加减乘除和开根号，时间复杂度可以看成O(1)，如果按二进制位数来算时间复杂度是O(log(m1+m2))。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

inline int lowBit(int x)
{
    return x & -x;
}

int main()
{
    std::vector<int32_t> v = {1, 3, 2, 3, 4};
    uint32_t n = v.size();
    std::vector<int32_t> r(n), a = v, t = v;

    // 离散化
    std::sort(t.begin(), t.end());
    for (int &num : a)
    {
        num = std::lower_bound(t.begin(), t.end(), num) - t.begin() + 1;
    }
    std::vector<int32_t> tree(n + 1, 0);
    for (uint32_t i = 0; i < n; i++)
    {
        int32_t q = a[i];
        q -= 1; // 不包括本身
        while (q)
        {
            r[i] += tree[q];
            q -= lowBit(q);
        }
        q = a[i];
        while (q < tree.size())
        {
            tree[q] += 1;
            q += lowBit(q);
        }
    }
    for (auto &i : r)
        std::cout << i << " ";
    return 0;
}