理解题目
这个题目一大障碍应该是理解题目，毕竟咱们的老妈不说英语。。。
题目的意思是这样的：
假设我们有一个整数商店，这个商店的商品是一个个的整数区间（线段）, 比如线段[2,4]代表打包出售数字[2, 3, 4], 同理[7,8]代表打包出售[7,8], 每个线段都一个价格C, 同时商店推出优惠活动，你购买了[2,4]和[7,8], 那么你现在拥有了数字[2, 3, 4, 7, 8] 商店会赠送你礼物数字5， 和6 赠送规则如下:
没有买x。
买了一个小于x的整数l。
买了大于x的整数r。
说白了就是中间缺的都会免费给你补上形成新的连续线段。
那么做为顾客，我们的目标是：
- 首先保证买到尽可能多的数字
- 在保证1的情况下花尽可能少的钱
但现在商店由于技术原因, 上架的n个线段只有前s个可供出售
所以说顾客只能在前s个线段中选择购买哪些
现在练习编码意图如下：
输入支持：
第一行输入一个数字 t 表明你要进行几次试验
然后就是进行t次试验的数据输入，其中每次试验需要输入如下数据
第一行输入商店总共有多少条线段出售n
然后循环输入每一条线段的参数 l, r, c一行代表一个线段(l起点， r终点， c售价)
注意，题目中对参数有值域限定，编程中应有所体现
讲道理我们大多数时候都是在做各种限定，各种检测，异常处理，真正的算法其实没多少东西，甚至说很简单。
值域限定容易理解，虽然写起来挺啰嗦的，其中一条我理解的未必准确
It is guaranteed that the total sum of n over all test cases doesn't exceed 2⋅10^5
这是英文，我理解的是所有输入的n的总和不超过2*10^5(实例代码有体现)
输出要求:
前边我们说了，在n个待售线段中由于技术原因只有前s个可供出售
那么输出方面就是让你分别设定这个s 从1-n， 然后给出在当前s值下，用户需要消费多少钱买到最多的数字
举例来说 假设当前商店出售的n=2个线段 分别为[1,4] 20块钱 [7,8] 30块钱，那么你应该输出
20//s=1时能买到1,2, 3, 4
50//s=2时能买到1, 2, 3, 4...8
好了题目说清楚了，再说说算法
首先我们必须在不考虑价格情况下找出能买到的最多的数字，那就找到s个线段中最小和最大的数字
有了这两个数字，根据贪心原理 在找到拥有最小数字最便宜的线段 和拥有最大数字最便宜的线段，这俩个价格相加即为我们最终消费（如果是同一个线段则无需加了）
那么算法和环境输入输出条件都有了, 剩下就是具体编码练习了，本例输出是固定的，所以错就是错，对就是对.
有兴趣的同学可以和c代码比较下，看看哪个更简洁明了
具体编码
import kotlin.math.pow
/**
* Accomplished using the EduTools plugin by JetBrains https://plugins.jetbrains.com/plugin/10081-edutools
*
* To modify the template, go to Preferences -> Editor -> File and Code Templates -> Other
*/
/**
* 线段数据类
* 并且为了方便写了一个扩展函数
*/
data class Segment(val l:Long, val r:Long, val c:Long){
fun checkValid(){
val range = 1..1E9.toLong()
check(l in range)
check(r in range)
check(c in range)
check(r >= l)
}
}
fun List<Long>.toSegment()= run {
check(this.size==3)
Segment(this[0], this[1], this[2]).also {it.checkValid()}
}
/**
* 读取一个线段类
*/
fun readSegment() = readLine()!!
.split(' ')
.map { it.toLong() }
.toSegment()
fun main() {
// Write your solution here
// 输入支持
// 输入实验次数
val t = readLine()!!.toInt()
check(t in 1..1_000)//值域检测
//循环读取各个实验的数据
val inputs = (1..t).map {
val n = readLine()!!.toLong()
check(n in 1..1E5.toLong())
//循环读取线段数据
(1..n).map {
readSegment()
}
}
//n 的总是不能超过2*10^5检测
check(inputs.sumOf { it.size }<=2E5)
// 上面这一堆代码实际上都是在满足练习题的输入要求
// 包括各种检测，具体算法其实简单的一B
for(segments in inputs){
(1..segments.size).map {s->
segments.subList(0, s).run {
//找出最小和最大的整数
val minInt = minOf { it.l }
val maxInt = maxOf { it.r }
//找到拥有最小整数并且售价最低的segment
val segWithMin = this.filter { it.l == minInt }
.minByOrNull { it.c }
//同理找到max
val segWithMax = this.filter { it.r == maxInt }
.minByOrNull { it.c }
//输出结果
if(segWithMax!!.l != minInt && segWithMax != segWithMin){
println(segWithMax!!.c + segWithMin!!.c)
}
else{
println(segWithMax!!.c)
}
}
}
}
}
如果确实阅读了这个代码，我们会发现算法的代码就那么几行，剩下的全是输入输出和各种检测。 虽然这是练习题，但我看这很符合实际开发的情况，当然实际开发中会更复杂一些， 现在仅仅是调用了个check函数而已，实际肯定要做处理的。
和前边一样， 那我们在思考一下 上述代码还有没有什么好的改进意见？
很遗憾，本人没想到太好的优化策略，最多也就是多加个条件判断提前退一下循环。意义不大。
网友评论