题解 P2947 【[USACO09MAR]向右看齐Look Up】
Iowa_BattleShip
2018-03-05 21:04:32
看看题解里竟然没有单调队列的题解,而这题标签却有单调队列……所以我来补一发吧。
单调队列的解法目前不加register和inline,就只有快读,不开O2只要40ms就能过,还是比较快的,毕竟O(n)算法。
具体算法解释看代码吧
```cpp
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],q[N],an[N];//a是原数,q是队列,用来储存队列中数在数组a的下标,an则储存答案
int re()//快读
{
int x=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+(c-'0');
return x;
}
int main()
{
int i,n,tail=0;//这题不需要head,因为没有区间大小,head一直为1
n=re();
for(i=1;i<=n;i++)
a[i]=re();//输入
for(i=1;i<=n;i++)
{
while(tail&&a[i]>a[q[tail]])//单调队列模板打法,因为head为1,所以要保证tail>0,当目前扫到的数大于队列末尾的数时,这个数一定是队列末尾这个数右端第一个比它大的数,所以就把这个这个数储存入队列末尾数的an数组中,并将tail--,即把末尾数移除队列,紧接着比较队列中下个数,直到遇到第一个≥这个数或队列空为止。 总的核心思想就是维护一个不上升连续序列,在维护的同时找到答案
{
an[q[tail]]=i;
tail--;
}
q[++tail]=i;//将这个数加入队列
}
for(i=1;i<=n;i++)
printf("%d\n",an[i]);//最大的数和最后的一个不上升连续序列的数对应的answer是不会修改的,所以放心直接输出
return 0;
}
```