111qqz的小窝

老年咸鱼冲锋!

zoj 3606 Lazy Salesgirl (线段树,单点更新,区间合并)

zoj3606题目链接

题意:有个小女孩卖火柴,有n个人会来买,分别在时间t[i],以价格p[i],买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴,小女孩就会睡着。小女孩睡着后如果有人来买火柴,那小女孩就会醒过来,但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

思路: 显然,w应该是某2个顾客的来访时间只差(而不是什么任意值).

因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。

我们可以从小到大枚举w,这样就可以保证得到的最大营业额的对应w最小。

构造一颗线段树,维护4个域,cnt表示区间中,确实购买了火柴的顾客的人数,sum[i] (i属于0..2) 表示一个区间中最左边的顾客购买了i+1根火柴后,该区间的最大利润。

所以其实这道题类似hdu4288解题报告           

维护sum[i]的时候,右一点绕,需要注意对于tree[rt].sum[i],我们只是说该区间的最左边的人买了(i+1)根火柴,该区间的其他人买了几根火柴无所谓,我们只想知道该区间的利润。

wa了一次。。因为虽然我们分析出w一定是某2个连续的时间的差值,一定是整数值,但是为了迷惑人。。题目还是要以6位小数输出。

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz