- OJ-ID:
- CodeForces-479D
- author:
- Caution_X
- date of submission:
- 20191109
- tags:
二分, 贪心
description modelling:
有一把尺子, 尺子上有 n 个刻度 A[i], 问能否通过已知的刻度测出长度 x 和长度 y?
输出需要补充的刻度点个数和对应的值
major steps to solve it:
需要补充的刻度点数只能是 0,1,2
需要补充的点数为 0 时可以直接判断
判断能否只补充一个刻度点:1记 tx=A[i]+x, 表示可以在 A[i]右边得出一个刻度能够测出 x
再二分查找判断 (tx+y) 或者 (tx-y) 在不在已知刻度中, 若在, 则一个刻度点 tx 即可, 同理,2记 ty=A[i]+y,
重复类似1的操作, 只要1,2有一个满足条件即可, 若都不满足时: 记 tx=A[i]-x, 表示能够在
刻度点 A[i]左边找到一个刻度点测出 x, 记 ty=A[i]-y, 同理操作. 若通过上述操作能够找出, 则
只需要补充一个刻度点, 否则, 需要补充两个刻度点.
warnings:
重点在于点数 1 和点数 2 的判断, 点数 1 需要特判
比如 x=6,y=7, 已知的刻度点有 4,5, 那么只要补充一个刻度点 11 即可
来源: http://www.bubuko.com/infodetail-3280474.html