Energy stones

题意

有n块石头,每块有初始能量E[i],每秒石头会增长能量L[i],石头的能量上限是C[i],现有m次时刻，每次会把[s[i],t[i]]的石头的能量吸干，问最后得到了多少能量？

分析

题意不难理解，模拟题意也不难,但是纯粹模拟会T上天,怎么处理呢？枚举时间不可行，我们可以换个角度思考问题，考虑求每一个石头的贡献行不行？如何求一个石头的贡献呢，只要知道哪个时间点吸了这个石头，就能求出这个石头的贡献了。那时间点如何维护？我们知道，相邻石头的时间点不同只可能是有终点或者起点在相邻的石头中出现，所以时间点可以很好得转移。那么石头贡献怎么算？对于一个石头，如果他的时间段已知，我们记录每个段长度的数量以及时间的总和,对于一个石头,长度可以分成两种情况：设从0开始吸收的能量小于C[i]的时间长度为 d=C[i]/L[i]那么 对于时间段中小于等于d的段来说，只要把这些段的时间乘以该石头的L[i]，即可，而对于大于d的段来说，这些段能量都已经叠到上限了，只要把段数乘以C[i]就是这一段的贡献。那么初始有能量怎么办？只要把这一段提出来，特殊处理即可。如果维护小于d的段的数量以及时间？可以使用树状数组(这题卡常，线段树不行)，那时间段怎么维护？可以使用set

代码借鉴自咖啡鸡，咖啡鸡

最新文章

1. ar命令详解
2. 20145212 《Java程序设计》第8周学习总结
3. java类的加载过程
4. 修改datagridview中其中一列的值
5. 深入分析：Android中app之间的交互(一，使用Action)
6. HTTP协议的安全性--全站HTTPS
7. POJ 3422 Kaka's Matrix Travels K取方格数
8. 【转】使用Memcached提高.NET应用程序的性能
9. hdu 4335 What is N?
10. JavaScript入门(6)
11. 9款超酷的jQuery/CSS3插件
12. HTML、CSS、JS 样式
13. 80端口被系统服务【kernel&System】占用解决方案
14. CSS3学习笔记--media query 响应式布局
15. 洛谷P3381 - 【模板】最小费用最大流
16. 分享自己用的php分页类实例源码
17. What can Reactive Streams offer EE4J?
18. elastic-job详解（一）：数据分片
19. 应用程序发生异常 unknown software exception (0xc00000fd)... - 栈溢出(Stack overflow)
20. Unity3D 重写下拉菜单/Dropdown组件、开启每个按钮可用

热门文章

1. PHP0012：PHP操作文件目录
2. JMeter接口测试-跨线程组取参数值的两种方法
3. USB-Blaster CPLD FPGA Intel 驱动安装不上的问题，文件的哈希值不在指定的目录文件中，的解决办法，其实很简单
4. 木兰国产编程语言 Mulan--附带下载地址
5. redis深入学习
6. 吴裕雄--天生自然 R语言开发学习：集成开发环境\工具RStudio的安装与配置
7. java【第三课 条件语句】
8. STL-deque 双端数组简析
9. 数据库中间件DBLE学习(一) 基础介绍和快速搭建
10. LeetCode 9、判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。