<head>
<meta charset="UTF-8">
<title>历届试题 区间移位</title>
</head><p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【问题描述】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">数轴上有</span><i><span lang="EN-US">n</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">个闭区间</span><i><span lang="EN-US">D</span></i><sub><span lang="EN-US">1</span></sub><span lang="EN-US">,</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">…</span><span lang="EN-US">,<i>D<sub>n</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。其中区间</span><i><span lang="EN-US">D<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">用一对整数</span><span lang="EN-US">[<i>a<sub>i</sub></i>, <i>b<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">来描述，满足</span><i><span lang="EN-US">a<sub>i</sub></span></i><span lang="EN-US"> < <i>b<sub>i</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">。已知这些区间的长度之和至少有</span><span lang="EN-US">10000</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">。所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖</span><span lang="EN-US">[0, 10000]</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">——也就是说</span><span lang="EN-US">[0, 10000]</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">这个区间内的每一个点都落于至少一个区间内。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">具体来说，假设你将</span><i><span lang="EN-US">D<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">移动到</span><span lang="EN-US">[<i>a<sub>i</sub></i>+<i>c<sub>i</sub></i>, <i>b<sub>i</sub></i>+<i>c<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">这个位置。你希望使得</span><span lang="EN-US">max<i><sub>i</sub></i> |<i>c<sub>i</sub></i>|
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">最小。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【输入格式】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">输入的第一行包含一个整数</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，表示区间的数量。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">接下来有</span><span lang="EN-US">n</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">行，每行</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">个整数</span><span lang="EN-US">a<sub>i</sub>,
b<sub>i</sub></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，以一个空格分开，表示区间</span><span lang="EN-US">[<i>a<sub>i</sub></i>, <i>b<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">。保证区间的长度之和至少是</span><span lang="EN-US">10000</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【输出格式】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">输出一个数，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【样例输入】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI1"><span lang="EN-US">2<o:p></o:p></span></p>
<p class="NOI1"><span lang="EN-US">10 5010<o:p></o:p></span></p>
<p class="NOI1"><span lang="EN-US">4980 9980<o:p></o:p></span></p>
<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【样例输出】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI1"><span lang="EN-US">20<o:p></o:p></span></p>
<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">【样例说明】</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">第一个区间往左移动</span><span lang="EN-US">10</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">；第二个区间往右移动</span><span lang="EN-US">20</span><span style="font-family:宋体;mso-ascii-font-family:"Times New
历届试题.zip （56个子文件） 
历届试题 
历届试题 格子刷油漆.html 1KB 历届试题 分糖果.html 1KB 历届试题.html 5KB 历届试题 危险系数.html 2KB 历届试题 日期问题.html 2KB 历届试题 回文数字.html 2KB 历届试题 幸运数.html 2KB 历届试题 小数第n位.html 1KB 历届试题 公式求值.html 2KB 历届试题 剪格子.html 2KB 历届试题 数组操作.html 8KB 历届试题 高僧斗法.html 2KB 历届试题 包子凑数.html 3KB 历届试题 斐波那契.html 1KB 历届试题 网络寻路.html 2KB 历届试题 蚂蚁感冒.html 2KB 历届试题 k倍区间.html 2KB 历届试题 约数倍数选卡片.html 2KB 历届试题 国王的烦恼.html 2KB 历届试题 带分数.html 1KB 历届试题 买不到的数目.html 1KB 历届试题 打印十字图.html 2KB 历届试题 最大子阵.html 1KB 历届试题 正则问题.html 2KB 历届试题 合根植物.html 2KB 历届试题 观光铁路.html 3KB 历届试题 分巧克力.html 2KB 历届试题 油漆面积.html 3KB 历届试题 兰顿蚂蚁.html 3KB 历届试题 农场阳光.html 2KB 历届试题 拉马车.html 4KB 历届试题 发现环.html 1KB 历届试题 横向打印二叉树.html 2KB 历届试题 车轮轴迹.html 5KB 历届试题 矩阵翻硬币.html 2KB 历届试题 九宫幻方.html 3KB 历届试题 数字游戏.html 2KB 历届试题 地宫取宝.html 2KB 历届试题 波动数列.html 2KB 历届试题 区间移位.html 12KB 历届试题 翻硬币.html 1KB 历届试题 Excel地址.html 2KB 历届试题 连号区间数.html 1KB 历届试题 分考场.html 1KB 历届试题 邮局.html 2KB 历届试题 大臣的旅费.html 2KB 历届试题 核桃的数量.html 1KB 历届试题 九宫重排.html 1KB 历届试题 青蛙跳杯子.html 3KB 历届试题 错误票据.html 2KB 历届试题 小计算器.html 2KB 历届试题 城市建设.html 3KB 历届试题 填字母游戏.html 2KB 历届试题 对局匹配.html 1KB 历届试题 图形排版.html 4KB 历届试题 小朋友排队.html 2KB
评论0
最新资源