蓝题5pts求调,感觉没什么问题呀(单调栈)
查看原帖
蓝题5pts求调,感觉没什么问题呀(单调栈)
592916
aurshine楼主2024/3/17 23:29

先从第一颗树飞,然后用瞬移卡,每次选可以飞的次数最多且可以瞬移到的树瞬移

#include <iostream>
#include <algorithm>

using namespace std;
using PII = pair<int, int>;
using LL = long long;

constexpr int N = 3e5 + 10;

int n, m;
int tree[N], card[N], l[N], r[N];
int q[N], tt;
PII a[N];

int max_skip(int u)
{
    return max(l[u], r[u]);
}

int find(int x)
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (a[mid].first <= x)  l = mid;
        else r = mid - 1;
    }
    
    return l;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
        cin >> tree[i];
    
    for (int i = 0; i < m; ++ i)
        cin >> card[i];
    
    for (int i = 0; i < n; ++ i)
    {
        int h = 0;
        while (tt && tree[q[tt - 1]] < tree[i])    h = max(h, l[q[-- tt]] + 1);
        l[i] = h;
        q[tt ++] = i;
    }

    tt = 0;
    for (int i = n - 1; i >= 0; -- i)
    {
        int h = 0;
        while (tt && tree[q[tt - 1]] < tree[i])    h = max(h, r[q[-- tt]] + 1);
        r[i] = h;
        q[tt ++] = i;
    }
    
    for (int i = 0; i < n; ++ i)    a[i] = {tree[i], max_skip(i)};
    sort(a, a + n);
    for (int i = 1; i < n; ++ i)
    {
        a[i].second = max(a[i].second, a[i - 1].second);
    }
        
        
    LL res = max_skip(0);
    for (int i = 0; i < m; ++ i)
        res += a[find(card[i])].second;
    
    cout << res;
}
2024/3/17 23:29
加载中...