文档章节

[PA2015]Siano 单调栈

o
 osc_b71hj3or
发布于 07/05 08:23
字数 1496
阅读 14
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

由于某人找了个单调栈的题解但是没研究透所以让我们来研究。。。。。。。。。。。。

首先先来考虑下面一种情况,假设第\(k\)次切割时,天数为\(d_k\),高度为\(b_k\),第\(k+1\)次切割时,天数为\(d_{k+1}\),高度为\(b_{k+1}\),那么我们定义一个切割速度,令\(v=\frac{b_{k+1}-b_k}{d_{k+1}-d_k}\),这个切割速度有什么含义呢,如果在\(d_k\)天时所有的草都是\(b_k\)高,那么生长速度\(>v\)的草都要割掉,注意这里的\(v\)极有可能是一个浮点数,而在写代码的时候最好还是避免浮点数的出现,所以要怎么转化?这个应该很显然,令\(v=\lfloor \frac{b_{k+1}-b_k}{d_{k+1}-d_k} \rfloor\)即可,因为判断的时候都是找的大于这个\(v\)的,而给出的生长速度都是整数,所以把这个\(v\)下取整后再判断大小也没有任何影响。怎么求出答案呢?很显然,就是\((d_{k+1}-d_k)*\)需要割掉的草的总生长速度\(+t\)\(t\)是什么?分类讨论一下,如果\(b_k>b_{k+1}\),那么除了长出来的草,还需要割掉\(b_k\)\(b_{k+1}\)高的那一段,也就是\((b_k-b_{k+1})*\)需要割掉的草的总数量,如果\(b_k==b_{k+1}\)\(t=0\),如果如果\(b_k<b_{k+1}\),就不能长出来的全都割掉,因为只割到\(b_{k+1}\),所以需要把之前多算的那些减去,即\(-(b_{k+1}-b_k)*\)需要割掉的草的总数量,综上所述,\(t=(b_k-b_{k+1})*\)需要割掉的草的总数量,于是需要求的就是需要割掉的草的总生长速度和需要割掉的草的总数量,注意到\(m\)最大也就\(10^6\),所以开\(10^6\)个桶,第\(i\)个桶里边存生长速度为\(i\)的草的数量,然后就可以运用一下前缀和的思想求出上边的两个值。

好了基本思想有了,但是注意一个问题,并不是所有的需要切割的草在上一次切割时都恰好为\(b\),即上一次没有被切割但是下一次它长到了可以被切割的高度的草,把这些草。所以上边讨论了五百多字就白扯了吗,显然不是,还是有一部分草是满足上述的切割办法的,也就是两次都被切割的,所以只需要特殊考虑上一次没有被切割但是下一次它长到了可以被切割的高度的草,把这些草处理了就行。通过上一次的切割处理这个很不好处理,但是我们可以发现,如果我们定义第0天时割掉了所有高度大于0的草(对答案没有影响因为初始时都是0),那么假设当前时刻为\(d_k\),这些草在之前的某个时刻\(d_t(d_t \in[0,d_k)\ \ )\)一定会被割掉,于是\(d_t\)\(d_k\)套用上述式子就行,聪明的你一定会发现这样会重复割草,没错,的确会,为了避免这种情况,假设上次割掉了生长速度超过\(last\)的草,那么这次只需要割掉生长速度超过切割速度且小于等于\(last\)的草即可,但是这样还是会出现重复割草的情况,因为可能前边已经割过的又被割了一次,所以需要记录前边每一次割草割过的最小切割速度,举个例子吧,假设记录的这个为\(to_i\),表示的意思就是在第\(i\)次割草的时候生长速度大于\(to_i\)的已经都被割掉了,所以如果此时\(k-i\)的切割速度大于\(to_i\)就需要直接\(break\)掉,避免了重复割草。
但是这样做的时间复杂度应该是\(O(m^2)\)的,需要优化一下。

注意到草的生长速度是有单调性的,在不去割草的情况下生长速度越大的高度一定越大废话,于是可以维护一个\(to\)值单调上升的单调栈。若栈顶那一次切割能切到的最小速度\(\leq\)当前能切到的最小速度,则前面切不到的依旧切不到,若栈顶那一次切割能切到的最小速度\(>\)当前能切到的最小速度,则先计算比栈顶那一次切割能切到的最小速度大的,并将栈顶\(pop\)掉,重复此过程至栈顶速度\(\leq\)当前能切到的最小速度。

但是这样会不会漏掉什么情况呢?答案是不会,因为每一次的割草都是割的连续的速度,只可能出现重复情况,而重复情况上边已经排除,所以这种做法是可以的。

由于本人蒟蒻,可能有些地方写的不严谨或者不清楚,又或者有的地方写错了。。。反正感觉不对的地方欢迎指出来。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int lqs=5e5+10,m=1e6;
int day,a[lqs<<1],n,stk[lqs],top;
ll s[lqs<<1],d[lqs],b[lqs],to[lqs];
int main(){
	scanf("%d%d",&n,&day);
	for(int w,i=1;i<=n;i++)
		scanf("%d",&w),a[w]++;
	for(int i=1;i<=day;i++)
		scanf("%lld%lld",&d[i],&b[i]);
	for(int i=1;i<=m;i++)
		s[i]=s[i-1]+1ll*a[i]*i;
	for(int i=1;i<=m;i++)
		a[i]+=a[i-1];
	top=1;
	for(int i=1;i<=day;i++){
		ll res=0;
		int last=m,x=max(to[stk[top]],min((b[i]-b[stk[top]])/(d[i]-d[stk[top]]),1ll*m));
		while(x<last){
			res+=(d[i]-d[stk[top]])*(s[last]-s[x])+(b[stk[top]]-b[i])*(a[last]-a[x]);
			last=x;
			if(last>to[stk[top]])break;
			if(top==0)break;top--;
			x=max(to[stk[top]],min((b[i]-b[stk[top]])/(d[i]-d[stk[top]]),1ll*m));
		}
		to[i]=last;
		if(to[i]<m)stk[++top]=i;
		printf("%lld\n",res);
	}
}
o
粉丝 0
博文 59
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.1K
1
个人计算机操作系统--eComStation

eComStation(简写为 eCS)是一款基于OS/2,由Serenity Systems发布的个人计算机操作系统。它包含了一系列在OS/2的IBM版本中没有的组件及应用。 eComStation的最初版本v1发布于2001年,基于I...

匿名
2013/03/26
3K
0
VCTransitionsLibrary –自定义iOS交互式转场动画的库

简介 VCTransitionsLibrary 提供了许多适用于入栈,出栈,模态等场景下控制器切换时的转场动画.它本身提供了一个定义好的转场动画库,你可以拖到自己工程中直接使用;也提供了许多拥有不同转场动...

ios122
2015/08/27
2.9K
0
如何给Vanilla(OpenResty)添加一个路由协议

源起 QQ群经常看到有同学问(Vanilla/OpenResty开发:205773855,OpenResty技术交流2群:481213820): 如何让Vanilla支持Restful(或者Vanilla如何支持xxxx样子的URL访问)? Vanilla的路由...

iDev_周晶
2016/01/16
990
1
【腾讯Bugly干货分享】Android APP 快速 Pad 化实现

 项目背景 采用最新版本手机 APP(之后称为 MyApp)代码,实现其 Pad 化,为平板和大屏手机用户提供更好的体验。为实现 MyApp 的 Pad 化工作,需要我们首先来了解一下 MyApp 项目经典页面的构...

腾讯Bugly
2016/03/18
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Java中使用OpenSSL生成的RSA公私钥进行数据加解密

当前使用的是Linux系统,已经按装使用OpenSSL软件包, 一、使用OpenSSL来生成私钥和公钥 1、执行命令openssl version -a 验证机器上已经安装openssl openssl version -a 运行结果: 2、生成...

osc_1psr53ow
29分钟前
7
0
计算机毕业设计之springboot+vue.js点餐小程序 点餐系统

功能 后台: 1. 超级管理员(具有该系统所有权限)登录 查看系统所有管理员 操作:可新添加管理员并分配系统已有角色; 可对已有管理员进行信息编辑; 可对除超管外的其他管理员账号禁用/启用...

osc_x4ot1joy
31分钟前
10
0
MATLAB数学建模

链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy2 记录matlab参加建模比赛时所用的书籍,避免忘记 链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy...

osc_oa6qrgun
32分钟前
6
0
Python中可以使用静态类变量吗? - Are static class variables possible in Python?

问题: Is it possible to have static class variables or methods in Python? Python中是否可以有静态类变量或方法? What syntax is required to do this? 为此需要什么语法? 解决方案:...

技术盛宴
今天
17
0
如何在Android中以像素为单位获取屏幕尺寸 - How to get screen dimensions as pixels in Android

问题: I created some custom elements, and I want to programmatically place them to the upper right corner ( n pixels from the top edge and m pixels from the right edge). 我创建......

javail
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部