首页 > 代码库 > 最大数——栈
最大数——栈
洛谷 P1198 [JSOI2008]最大数
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入输出格式
输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入样例#1：
5 100A 96Q 1A 97Q 1Q 2
输出样例#1：
969396
说明
[JSOI2008]
思路
模拟一个单调递减栈，（和上一题思路一致）如果后加入的书比他前面的数大，那就把这个数弹出栈，然后用二分答案的方法求最大值所在的区间。
其实这个题还可以用单调队列的在这里我就不详细说了
http://hzwer.com/1130.html
黄学长博客有
代码
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100000#define maxn 123456using namespace std;int n,d,t,m;char ch;int top,stack[N],a[N],len;/* 维护一个递减栈的原因： 考虑两个是ai和aj，如果i>j,并且ai>aj的话， 那么我们可以发现j没有任何存在的意义了。 因为如果aj可以作为最终答案的话，一定就会经过ai。 然后就不可能选aj了。*/int main(){ scanf("%d%d",&n,&d); for(int i=1;i<=n;i++) { cin>>ch>>m;//不能使用 scanf("%c%d",&ch,&x);因为scanf( )读入换行，cin不读入换行！ if(ch==‘A‘)//加入一个新点的情况 { m=(m+t)%d;//t为上一次输出的最大的那个值 a[++len]=m;//a[i]数组中直接存数 while(top&&a[stack[top]]<=m) top--; stack[++top]=len;//stack[]中存单调递减+序列的数的编号 } else { int l=1,r=top; while(l<r) { int mid=(l+r)/2; if(stack[mid]<len-m+1) l=mid+1; else r=mid; } int y=l; t=a[stack[y]]; printf("%d\n",t); } } return 0;}
最大数——栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。