题意

　　有n(n<=3000)个人参与acm比赛，每个人都有一个解题数，现在要决定拿金牌的人数cnt1，拿银牌的人数cnt2，拿铜牌的人数cnt3，各自对应一个解题数区间[d1,c1],[d2,c2],[d3,c3]

　　现在要求：

　　　　1、d1-c2尽可能大

　　　　2、在1满足的前提下，d2-c3尽可能大

　　　　3、在1,2满足的前提下，d3-num尽可能大(num表示铁牌第一名的解题数)

　　　　4、对于任意的x,y(1<=x,y<=3)，cntx<=2*cnty

　　你需要给出一种每个人的奖牌分配来满足以上要求(1,2,3,-1分别表示金银铜铁)

分析

　　一个直接的想法就是暴力枚举金银铜的线，然后去得到最优的结果，这样是$O(n^3)$的，会超时

　　范围其实并不大，应该是可以$O(n^2)$解决的

　　我们可以只枚举金牌线和银牌线，快速计算铜牌线应该在哪

　　我们知道了cnt1和cnt2的值，于是就知道了cnt3的取值范围，就知道了铜牌线的区间[l,r]

　　我们需要在这[l,r]内找一个k，使得a[k]-a[k+1]的值最大

　　很容易想到求个差分数组，多次询问差分数组在[l,r]范围内的最大值，所以直接rmq

　　时间复杂度$O(n^2)$

最新文章

1. Alpha阶段总结
2. 浅谈HTML5单页面架构（二）——backbone + requirejs + zepto + underscore
3. Redis数据库入门教程
4. Raspberry pi(-) Mac下安装系统
5. Python.Django视频教程（全13集）
6. thinkphp验证码的实现
7. nau8822 codec driver 录音时mic bias 无法自动打开问题
8. The following module was built either with optimizations enabled or witherout debug information
9. linux学习笔记之文件类型，及目录介绍
10. Linux sftp 另外一台机器时，出现:receive message is too long
11. [济南集训 2017] 求gcd之和
12. 批处理基础知识-IF
13. Google Chrome 书签导出并生成 MHTML 文件
14. 扒一拔：Java 中的泛型（一）
15. springmvc学习路线1-基本配置
16. Android中的Sqlite中的onCreate方法和onUpgrade方法的执行时机
17. linux下文件共享的几种常用方式
18. python 爬虫资料
19. 8 -- 深入使用Spring -- 3...1 Resource实现类ServletContextResource
20. 采用Post方式提交数据实例

热门文章

1. centos7 搭建双网卡bond1（主备模式）实例
2. zabbix设置发送消息的时间
3. 小程序02 wxml和wxss
4. 从零开始--系统深入学习Android
5. CodeForces - 1105D Kilani and the Game(多源BFS+暴力)
6. [CF] 474 F. Ant colony
7. 7. ENGINES
8. 树莓派 - MQTT
9. 南邮CTF--bypass again
10. LeetCode（86） Partition List