0816 京东笔试答案

0816 京东笔试答案

第一题, 减少逆序对数量

对于每个 ai, 找到 所有 aj = a[i] + 1 且 j < i 的 j, 则对于选择 j < L <= i 的 L 贡献 +1, 然后做一个前缀和取最大值即可

代码
```
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

void solve()
{
    int n; cin >> n;
    vector<int> a(n + 10, 0), b(n + 10, 0), c(n + 10, 0);
    unordered_map<int, vector<int>> pos;
    
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        int v =a[i];
        int t = v + 1;
        if (pos.find(t) != pos.end()) 
        {
            for (int j : pos[t])
            {
                if (j < i)
                {
                    b[j + 1] ++; 
                    b[i + 1] --;
                }
            }
        }
        pos[v].push_back(i);
    }
    
    int ans = 0;
    int tmp = 0;
    
    for (int i = 1; i <= n; i ++)
    {
        tmp += b[i];
        ans = max(ans, tmp);
    }
    
    cout << ans << endl;
    
}

int main()
{
    int _ = 1;
    cin >> _;
    while (_ --)
    {
        solve();
    }
}
```

第二题, 跳水打分

解法类似求区间最值, 维护每个长度为 m 的区间的最大值和最小值, 然后遍历过去即可算出答案。

代码
```
#include <bits/stdc++.h>

#define PII pair<long, long>
#define x first
#define y second

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<PII> maxPq;
    priority_queue<PII, vector<PII>, greater<PII>> minPq;
    
    vector<long long> a(n + 10);
    
    double ans = 0;
    long long tmp = 0;
    
    
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++)
    {
        maxPq.push({a[i], i});
        minPq.push({a[i], i});
        tmp += a[i];
    }
    long long minV = minPq.top().x;
    long long maxV = maxPq.top().x;
    ans = double(tmp - minV - maxV) / (m - 2);
    int ans2 = 1;
    
    int l = 1, r = m;
    while (r < n)
    {
        // cout << ans << endl;
        tmp -= a[l]; l ++;
        r ++; tmp += a[r];
        minPq.push({a[l], l}); minPq.push({a[r], r});
        maxPq.push({a[l], l}); maxPq.push({a[r], r});
        while (minPq.top().y < l) minPq.pop();
        while (maxPq.top().y < l) maxPq.pop();
        if ((double(tmp - minPq.top().x - maxPq.top().x) / (m - 2)) > ans)
        {
            ans = double(tmp - minPq.top().x - maxPq.top().x) / (m - 2);
            ans2 = l;
        }
    }
    cout << ans2 << endl;
}
```