CF 319B Psychos in a Line 【单调队列】

给出一排神经病的编号1-n的某个排列

给出规则

一步能同时消除该数右边连续的小于该数的数

问几步能消到最后状态

在纸上试了试,觉得这个问题很有点像lis,但是苦于方法

突然看了一眼tags

单调队列

oh it is

可以把这些数字一个一个的加入单调队列中

同时记录每个数字被吃掉的场次

保持整个队列递减

策略如下

如果一个数进去没有弹出数,则这个数肯定是第一场就被消掉的

如果一个数进去弹出了一些数,则该数被吃掉的场次等于它弹走的所有数中最大的被吃掉的场次序号+1

因为,这个数肯定是在它弹掉的数之后被吃掉的(它被弹完后的队列中最后面一个数吃掉)

如果一个数进去弹出了所有的数,则这个数被吃掉的场次为0

当然,一开始是要找到从第一个开始的单调子串中的最后一个数作为这个队列的第一个数,并且场次为0

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int NN=111111;
int f[NN];
struct Q{
	int x,pos;
}q[NN*10];
int main(){
#ifndef ONLINE_JUDGE
	freopen("G:/in.txt","r",stdin);
	//freopen("G:/myout.txt","w",stdout);
#endif
	int n,pos=0;cin>>n;
	for(int i=1;i<=n;i++)
		cin>>f[i];
	for(int i=2;i<=n;i++){//找到一开始递增的数串中最后一个数
		if(f[i]<f[i-1]){
			pos=i;
			break;
		}
	}
	if(pos==0){//全递增
		cout<<0<<endl;
		return 0;
	}
	int head=0,tail=0;
	int maxn=0;
    q[tail++]=(Q){f[1],1};
	for(int i=pos;i<=n;i++){
			if(f[i]<q[tail-1].x){//没有弹出数的是第一场就被吃掉的
				q[tail++]=(Q){f[i],1};
				maxn=max(q[tail-1].pos,maxn);
			}else if(f[i]>q[tail-1].x){//弹出数中最大场次+1是该数被吃掉的场次
			    int maxpos=0;
				while(f[i]>q[tail-1].x && tail>0){
                    maxpos=max(maxpos,q[tail-1].pos);
					tail--;
				}
				if(tail==0){
                        q[tail++]=(Q){f[i],1};
				}else{
                        q[tail++]=(Q){f[i],maxpos+1};
				}
				maxn=max(q[tail-1].pos,maxn);
			}
	}
	cout<<maxn<<endl;
	return 0;
}
 
时间: 08-27

CF 319B Psychos in a Line 【单调队列】的相关文章

Codeforces Round #189 (Div. 1) B. Psychos in a Line 单调队列

B. Psychos in a Line Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/problemset/problem/319/B Description There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who h

Codeforces 319B. Psychos in a Line【单调栈】

题目链接: http://codeforces.com/problemset/problem/319/B 题意: 一串数列,每一个值如果大于相邻右一位的值的话,那么就可以把右边这个值"吃掉"(右一位消失,原来的值不变),问需要吃多少次才能到达无法再吃的状态. 思路: 利用栈.遍历一遍数组,处理每个值的时候,如果栈顶的元素小于该值,那么将其弹出,知道栈顶元素大于该值或者栈为空,栈内的每个元素记录下一个属性:他是在第几次被"吃掉",进栈的新元素的被吃次数就是它弹出去的元

Codeforces 319B. Psychos in a Line【栈】

题目大意: 一串数列,每一个值如果大于相邻右一位的值的话,那么就可以把右边这个值"吃掉"(右一位消失,原来的值不变),问需要吃多少次才能到达无法再吃的状态. 做法: 利用栈.遍历一遍数组,处理每个值的时候,如果栈顶的元素小于该值,那么将其弹出,知道栈顶元素大于该值或者栈为空,栈内的每个元素记录下一个属性:他是在第几次被"吃掉",进栈的新元素的被吃次数就是它弹出去的元素中的属性的最大值+1,如果没有弹任何值则为1:如果栈空,则值为0: 代码: #include <

codeforces 251A Points on Line(二分or单调队列)

Description Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't e

单调栈/单调队列/RMQ

在上上周的交友大会中,队长大人提到了st算法,然后仔细的发呆了一个星期,于是就开始做队长的专题了, 6天后的我总算在此专题做题数目和队长一样了..明早没课,准备通宵把这几天的零散的记忆整理一下. HDU 3530 Subsequence 一开始想为何不能m和k一起放到while语句里进行处理 nowmax和nowmin保存了i之前的最大和最小值,假设此时已经出现不满足k和m的序列(A)了(比k大or比m小or both),然后我们往后找,发现了一个比序列(A)的min更小的值(me),此时now

HDU 4122 Alice&#39;s mooncake shop 单调队列优化dp

Alice's mooncake shop Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4122 Description The Mid-Autumn Festival, also known as the Moon Festival or Zhongqiu Festival is a popular harvest festival celebrated by Ch

POJ2823 Sliding Window(单调队列)

单调队列,我用deque维护.这道题不难写,我第二次写单调队列,1次AC. ----------------------------------------------------------------------------------- #include<cstdio> #include<cstring> #include<deque> #define rep(i,r) for(int i=0;i<r;i++) #define clr(x,c) memset

hdu 1506 Largest Rectangle in a Histogram 单调队列

Largest Rectangle in a Histogram Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12554    Accepted Submission(s): 3509 Problem Description A histogram is a polygon composed of a sequence of rec

[ACM] poj 2823 Sliding Window(单调队列)

Sliding Window Time Limit: 12000MS   Memory Limit: 65536K Total Submissions: 36212   Accepted: 10723 Case Time Limit: 5000MS Description An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left