单调队列+二分 G - Queue 小阳买水果

秒速五厘米 2021-09-30 02:10 232阅读 0赞

[B. Queue][]

这个题目会做的很偶然，突然想到的，因为我们要求离这只海象的最远的比他年轻的海象，这个年轻的海象可以用单调栈维护。

就是从前往后遍历一遍，单调栈里面存年龄从小往大的海象，这个为什么这么存呢，因为如果后面有比这个队列里面更年轻的海象，

那么就可以更新，而且这个更新是正确的，不会有影响，这个可以自己想一想/

然后就可以得到一个单调栈的数组，这个时候因为单调栈是单调的，所以可以用二分来查找我们所需要的值。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e5 + 10;
    typedef long long ll;
    int queue_min[maxn];
    int f1 = 1, t1 = 1, r = 1;
    int ans[maxn];
    ll num[maxn];
    ll a[maxn];
    
    int ok(ll s)
    {
        int x = 1, y = t1;
        int mid = (x + y) / 2;
        while(x<=y)
        {
            mid = (x + y) / 2;
            if (a[queue_min[mid]] >= s) y = mid-1;
            else x = mid + 1;
            //printf("x=%d y=%d mid=%d\n",x,y, mid);
        }
        //printf("mid=%d queue_min=%d\n", mid, queue_min[mid]);
        if (a[queue_min[mid]] >= s) return queue_min[mid - 1];
        return queue_min[mid];
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        f1 = 1, t1 = 1, r = 1;
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        queue_min[1] = 1;
        while(r<n)
        {
            r++;
            while (f1 <= t1 && a[r] < a[queue_min[t1]]) t1--;
            queue_min[++t1] = r;
        }
        for (int i = f1; i <= t1; i++) {
            num[i] = a[queue_min[i]];
            // printf("queue_min[%d]=%d\n", i, queue_min[i]);
            // printf("num[%d]=%lld\n", i, num[i]);
        }
        for(int i=1;i<=n;i++)
        {
            int f = ok(a[i]);
            //printf("F=%d\n",f);
            if (f < i) ans[i] = -1;
            else ans[i] = f - i - 1;
            printf("%d ", ans[i]);
        }
        printf("\n");
        return 0;
    }

单调栈 海象

[小阳买水果][Link 1]

这个题目和上面那个其实是一样的，但是我居然没有发现，这个要先前缀和处理一下，然后你就发现其实求的就是 比如 i ，求的就是 i 后面的比 i 更大的sum的最远位置。

也是二分+单调队列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 2e6 + 10;
    typedef long long ll;
    int queue_max[maxn];
    int a[maxn], num[maxn];
    ll sum[maxn];
    int f1, t1;
    int r;
    
    int ok(ll s) {
        int x = 1, y = t1;
        int mid = (x + y) / 2;
        while (x <= y) {
            mid = (x + y) / 2;
            if (sum[queue_max[mid]] > s) x = mid + 1;
            else y = mid - 1;
            //printf("x=%d y=%d mid=%d\n", x, y, mid);
        }
        //printf("mid=%d queue_min=%d\n", mid, queue_min[mid]);
        if (sum[queue_max[mid]] <= s) return queue_max[mid - 1];
        return queue_max[mid];
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &sum[i]);
            sum[i] += sum[i - 1];
        //    printf("sum[%d]=%lld\n", i, sum[i]);
        }
        f1 = 1, t1 = 1;
        r = 2;
        queue_max[1] = 1;
        int ans = 0;
        while (r <= n) {
            while (t1 >= f1 && sum[r] > sum[queue_max[t1]]) t1--;
            queue_max[++t1] = r;
            //printf("queue_max[%d]=%d\n", t1, queue_max[t1]);
            r++;
        }
        for (int i = f1; i <= t1; i++) {
            num[i] = sum[queue_max[i]];
            //printf("queue[%d]=%d\n", i, queue_max[i]);
        }
        for (int i = 1; i <= n; i++) {
            int f = ok(sum[i]);
            //printf("i=%d f=%d\n", i, f);
            if (f > i)
            {
                if (sum[i] >= 0) ans = max(ans, f - i + 1);
                else ans = max(ans, f - i);
            }
        }
        printf("%d\n", ans);
        return 0;
    }

二分+单调队列

转载于:https://www.cnblogs.com/EchoZQN/p/11195563.html

[B. Queue]: https://codeforces.com/problemset/problem/91/B
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/4879dcf57f9b4fa3b3d40119fe2fe191.png
[Link 1]: https://ac.nowcoder.com/acm/contest/949/D