题解 P2947 【[USACO09MAR]向右看齐Look Up】

Iowa_BattleShip

2018-03-05 21:04:32

Solution

看看题解里竟然没有单调队列的题解,而这题标签却有单调队列……所以我来补一发吧。 单调队列的解法目前不加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; } ```