分类 单调栈 下的文章

BZOJ 1345: [Baltic2007]序列问题Sequence

Solution单调栈水过。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 2000000; int stack[N], top; int main() { int n; scanf("%d", &n); long long ans = 0; for(int i=1; i<=n; i++) { int x; scanf(&- 阅读剩余部分 -

BZOJ 2086: [Poi2010]Blocks

Description给出N个正整数a[1..N],再给出一个正整数k,现在可以进行如下操作:每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后,问最大能够选出多长的一个连续子序列,使得这个子序列的每个数都不小于k。总共给出M次询问,每次询问给出的k不同,你需要分别回答。Input第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。第二行N个正整数,第i个正整数表示a[i] (a[i] <= 10^9)。第三行M个正整数,第i个正整数表示第i次询问的k (k &- 阅读剩余部分 -

BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节

题目描述输入Line 1: 牛的数量 N。Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。输出Line 1: 一个整数表示c[1] 至 c[N]的和。样例输入6 10 3 7 4 12 2样例输出5代码#include <cstdio> #include <algorithm> using namespace std; const int N = 90001; int a[N], s[N], tp; int sum[N]; int main() { //freopen("input", "- 阅读剩余部分 -

BZOJ 1657: [Usaco2006 Mar]Mooo 奶牛的歌声

题目描述Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。输入第1行:一个- 阅读剩余部分 -

BZOJ 3401: [Usaco2009 Mar]Look Up 仰望

题目描述约翰的N(1≤N≤105)头奶牛站成一排,奶牛i的身高是Hi(l≤Hi≤1,000,000).现在,每只奶牛都在向后看齐.对于奶牛i,如果奶牛j满足i<j且Hi<Hj,我们可以说奶牛i可以仰望奶牛j. 求出每只奶牛离她最近的仰望对象.输入第1行输入N,之后每行输入一个身高.N <= 10^5输出共N行,按顺序每行输出一只奶牛的最近仰望对象.如果没有仰望对象,输出0.样例输入6326112样例输出330660题解裸的单调栈,维护一个不下降的单调栈,遇到比当前高度小的弹栈就行了。代码#include <cstdio> #include- 阅读剩余部分 -