首页 > 其他分享 >blocks 单调栈、单调队列题解

blocks 单调栈、单调队列题解

时间:2024-02-22 11:00:28浏览次数:31  
标签:blocks 题解 ll long 端点 区间 单调 define

blocks题解:

1、题面:

image

2、分析:

题意大概就是说,找一段最长的区间,并且这段区间的平均值>=k,那么我们可以对他的每一个值减去k,最终求和>=0即可。
那我们需要对每个可能的左端点和右端点进行考虑,并以此让他们进行配对,看他们之间的区间和是否非负。
那么我们先定住一个右端点,再依次考虑可能的左端点即可,那么左端点一开始会很自然的想到是所有小于k的点的右一个点,但是这样可能会T,那么在让我们优化一下,依照从左向右顺序找出所有可能合法的区间,并将出了他的左端点以外的所有点排除(因为这些点还可以向左拓展)但是这太麻烦了,所以我们可以从左向右(以上一个不合法区间的右端点的下一个点作为下一个不合法区间的左端点)找出不合法的区间,那么除了左右端点以外的任一点到左端点这一段区间一定是合法的,因为它没有被纳入进来,然后就找出了所有可能的左端点。那么就往一个单调递减栈里面堆数,注意一开始要在栈里push 0 。

3、代码:

不开long long 见祖宗
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ps push_back
#define mk make_pair
#define fi first
#define se second
typedef pair<ll,ll> pii;
const ll N=1e6+10;
ll n,m,sum[N],k,a[N];
stack<ll> q;
void clear(){
	while(q.size())
		q.pop();
}
int main(){
	cin>>n>>m;
//	ll x;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	while(m--){
		cin>>k;
		clear();
		q.push(0);
		ll man=0;
		for(ll i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-k;
		for(ll i=1;i<=n;i++)if(q.empty()||sum[i]<sum[q.top()])q.push(i);
		for(ll i=n;i>=0;i--){
			ll jj=-1;
			while(!q.empty()&&sum[q.top()]<=sum[i]){
				jj=q.top();
				q.pop();
			}
			if(jj!=-1)man=max(man,i-jj);
		}
		cout<<man<<' ';
	}
	
}

标签:blocks,题解,ll,long,端点,区间,单调,define
From: https://www.cnblogs.com/GGrun-sum/p/18026721

相关文章

  • Blocks—单调栈
    思路:题目意思是求平均数>=k的最长序列先求出a[i]-k的前缀和就是求sum[i]-sum[j]>=0的最大i-j当j<=k<=isum[j]<=sum[k]j<=k<=isum[j]<=sum[k]更新i的时候,k就不如j优所以处理出来一个单调上升的数组(stak),那答案就在里面选倒序更新,单调栈一直减减就好因为如果用stak[top]更新了i,因......
  • [洛谷P3503][POI2010][BZOI2086]Blocks
    先看数据范围,n≤1e7,k≤1e9,暴力显然行不通,只能考虑单调栈;首先题目中说每一个数都要大于k,那么我们可以在初始化时就将每一个数都减去k,将问题转化为从正数中取出数加到负数里;然后维护一个前缀和,来判断一个区间是否符合要求;显然,当sum[j]-sum[i]≥0时,区间[i+1,j]符合题意,......
  • Blocks(单调栈)
    题干中说每次选择一个大于k的数,还要选他左右两个数其中之一加上一,最后问你最长的每个数不小于K的子序列。这些都是障眼法,其实就是问你最长的平均值大于或等于K的最长子序列,这样就明朗了。接下来就是找子序列的问题,因为要求的是区间最大平均值,所以不能再以单个数的值为依据来决......
  • 理想的正方形 题解
    题目描述有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。输入格式第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。100%的数据2<......
  • P5344 【XR-1】逛森林 题解
    题目链接:逛森林很早就想写写倍增优化建图,尤其是这题,奈何之前知识点没点够,本题线段树优化建图要优一些,不再赘述,没注意\(m\)是\(1e6\),挂了\(n\)多发才发现。后续再详细讲解倍增优化建图,这里简述本题做法。倍增优化建图其实和线段树优化建图恰不多的思想,为倍增求\(LCA\)的每......
  • 2024年2月21号题解
    106.从中序与后序遍历序列构造二叉树力扣题目链接解题思路找到根节点在中序序列的位置计算左子树的节点个数开辟一个节点,并把根节点的值赋值给这个节点根节点的左孩子和右孩子重复上面几个步骤代码实现/***Definitionforabinarytreenode.*structTreeNode{......
  • [BZOJ1047][HAOI2007][AcWing1091]理想的正方形(单调队列)
    此题的数据相当大,暴力的显然过不了,即使是O(abn)的算法也会超时,所以只能考虑O(ablogn)或O(ab)的算法。50分暴力#include<bits/stdc++.h>usingnamespacestd;intn,a,b,m[1001][1001];intdx(intx,inty){ intmaxn=0,minn=0x7fffffff; for(inti=x;i<=x+n-1;++i){ for(in......
  • Day-7 模拟赛题解
    Day-7模拟赛题解S+N---【玄英计划】---2月21日---模拟测#3【补题】-比赛-梦熊联盟T1数据点3-5枚举每一个问号对应的字母Kmp,把s当作模式串匹配T\(O(26^k|T|)\),k是?的个数代码(我也不知道为啥T了,鸽着)正解有种被诈骗了的感觉根据期望的可加性,答案等于......
  • P10064 [SNOI2024] 公交线路 题解
    非常好题目。思路可以发现限制最严的一定是两个叶子的联通性。我们不妨把一个叶子向外起到联通性作用的路径称为有用的路径。也就是这个叶子走这条路径一定可以两步以内到达任意点。这个路径集合有什么作用呢。有一个性质:整个集合的路径的交最终会形成一个连通块。那么我们......
  • Atm/抢掠计划——题解
    题目描述样例671223352441266510128161514435647解析题目明显是最长路,可以用spfa求最长路,但数据范围5e5明显不允许,所以我们可以用tarjan优化一下,然后这就变成了一道tarjan板子题,先用tarjan缩点,点权为几个点之和,把所有点再存到一个数组中,再按......