题解 P3522 【[POI2011]TEM-Temperature】

· · 题解

洛谷 P3522 题解

前置知识 单调队列

单调队列可以通过不断弹出已经无用的决策来维护队列内的递增或递减。

举个例子，如果 OI 只注重第一名，而且有个神犇既比我小又比我强，那么我就可以退役了。因为我能参加的比赛他也能参加，而我又拿不到第一名，这时就可以把我弹出 OI 的队列了。

还有一点，就是如果某个人已经上大学了，那么即使他提高组能拿满分，他也参加不了，因为他年龄太大了，这时也要把他弹出。

具体实现时可以维护一个双端队列，每次读入今年的新的选手，并从队头开始弹出年龄过大的人，再从队尾弹出比当前选手弱的人，最后把当前选手插入队尾，就可以维护出每一年的比赛谁会拿第一名（队头）。

题目大意

对每一天的天气都给出上界和下界，求最长可能有多少个连续天的温度不下降（注意是可能，不要求一定！）。

很显然，这一段的每一天的最高温度都必须大于这一天之前的最低温度最大值。

题目分析

根据上面的分析，可以得出需要维护当前这一天前面几天的最低温度最大值，这个最低温度就相当于选手有多强。那么年龄又是什么呢？可以发现如果当前这一天的最高温度小于这个人的最低温度，那么这个人就可以退役了，因为它无法再为这一道题的答案做贡献了。

具体实现

维护一个双端队列，先从队头开始弹出最低温度过大的天，此时更新一下 ans=\text{当前的天数}-\text{队头的天数}+1，再从队尾弹出所有比这一天的最低温度小的天（维护单调性）。为了维护比较方便，推荐使用结构体。

#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
struct node
{
    int l,r,id;//id表示是第几天
};
int main()
{
    int n,ans=1;
    scanf("%d",&n);
    deque<node> q;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        while(!q.empty()&&q.front().l>r)//要判断队列非空哦
        {
            q.pop_front();
        }
        if(!q.empty())
        {
            ans=max(ans,i-q.front().id+1);
        }
        while(!q.empty()&&q.back().l<l)
        {
            q.pop_back();
        }
        q.push_back((node){l,r,i});
    }
    printf("%d",ans);
    return 0;
}

如果这样做会发现样例都过不了，哪里出问题了呢？

如果有一天的最低温度特别大，把前面的所有天都弹出了，不代表就要重新从这一天开始计数啊，前面的天还是可以用的，弹出这几天只是为了维护单调性。所以可以在弹出时记录一下最后一个被弹出的天，并把它赋值给这一天的天数。这个天数就代表这一段是从哪一天开始的，并且结构体中记录着这一段的最低温度最大值。

AC 代码：

#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
struct node
{
    int l,r,id;//id表示是第几天
};
int main()
{
    int n,ans=1;
    scanf("%d",&n);
    deque<node> q;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        while(!q.empty()&&q.front().l>r)//要判断队列非空哦
        {
            q.pop_front();
        }
        if(!q.empty())
        {
            ans=max(ans,i-q.front().id+1);
        }
        int tmp=i;
        while(!q.empty()&&q.back().l<l)
        {
            tmp=q.back().id;//维护这一段的起始天
            q.pop_back();
        }
        q.push_back((node){l,r,tmp});
    }
    printf("%d",ans);
    return 0;
}

谢谢观看。