#P0817. 警钟长鸣

警钟长鸣

题目描述

故事背景(建议跳过):

一场决定命运的比赛,距离比赛结束还有50分钟...

选手Y,正面对一道决定他们队伍是否能拿到名额的“铜牌题”:

0 - 5分钟: 题目:《完美分割》 Y快速读完题:“哦!看起来是个经典的区间覆盖问题,可以用贪心解决。NN最大才10510^5,没问题。边界情况?嗯……应该就是开头和结尾要覆盖到。好了,思路清晰!” 他脑海中迅速构建了一个模型:“对每个点,我们选择能覆盖它的最远区间,这不就是JumpGameJump Game的变种吗?稳了。” 他没有在纸上详细验证一个复杂样例,也没有考虑当多个区间左端点相同且右端点不同时,他的“最远选择”策略是否会产生后效性问题。他感觉“灵光一现”,胜券在握。

6 - 10分钟: Y的手指在键盘上飞舞,带着一种“思路喷涌”的快感。他飞快地敲出了核心的贪心循环:

int pos = 1, ans = 0;
while (pos <= target) {
int nxt = pos;
	// 遍历所有左端点 <= pos 的区间,找到最大的右端点
	for (auto& seg : segments) {
		if (seg.l <= pos) {
			nxt = max(nxt, seg.r);
		}
	}
	if (nxt == pos) { // 没进步,说明覆盖不了
		cout << -1 << endl;
		return;
	}
	pos = nxt + 1; // 关键!他下意识地让pos跳到当前覆盖区间的下一个点
	ans++;
}
cout << ans << endl;

“一次通过!”他心想,并满怀信心地点击了“提交”。

11 - 50分钟:

第一次提交:Wrong Answer on test 3

Y愣住了。“样例都过了啊?”他赶紧手搓几组测试数据,发现是一个小Case。原来他的pos = nxt + 1跳得太快了,如果最优解需要区间恰好首尾相连(即一个区间的右端点等于下一个区间的左端点),他的算法会跳过这个连接点,导致多用了一个区间。 修复:“哦,简单,改成pos = nxt就好了。”他修改后再次提交。

第二次提交:Time Limit Exceeded on test 10.

复杂度不对!他猛然惊醒:在最坏情况下(所有区间左端点都是1),他那个forfor循环每次都会遍历全部区间,导致O(N2)O(N^2)的复杂度,而NN是10510^5。 修复:“需要优化,用个优先队列或者预处理一下。”他开始手忙脚乱地重写核心逻辑,引入一个按左端点排序的索引和指针来模拟优先队列。代码变得复杂起来。

第三次提交:Wrong Answer on test 15.

“又错?!”他心烦意乱。新的问题出现了:当有多个区间左端点相同时,他的新逻辑可能会过早地将某些区间弹出队列,从而错过更优的选择。他开始疯狂地printfprintf调试,在本地模拟那个让他出错的测试数据。 比赛倒计时在屏幕上跳动,队友投来关切而焦虑的目光。Y的额头开始冒汗。他最初的“清晰思路”现在变成了一团乱麻。他不断地打补丁:“是不是这里要加个等于号?” (if (seg.l <= pos) -> if (seg.l < pos))

推翻重来:“可能贪心是错的?要不要试试DP?”(但时间已经不够了)

玄学调试:“我把ans的初始值从00改成11试试?”

最终,在比赛结束的哨声响起前,他提交了第八次尝试。屏幕上弹出的依然是冰冷的 Wrong Answer on test 22。

赛后,在返回酒店的车上,队伍陷入沉默。

突然,Y的队友低声说:“你那道题,我看了一下。你最开始的想法是对的,就是JumpGameJump Game变种。但问题出在你的pos更新上。你想,如果区间是[1,5],[6,10][1, 5], [6, 10],你的算法会先把pos从11更新到55,然后发现没有左端点≤5\le 5的区间能覆盖66了,所以就出错了。其实应该预处理一个nxt数组,nxt[i]表示从位置i出发能跳到的最远位置……” Y听着,脑子里“轰”的一声。原来症结就在最初那10%10\%思考时忽略的一个细微但关键的逻辑漏洞。而他后来90%90\%的时间,都在为最初那个未经严谨推敲的、带着隐性BUG的模型,做着徒劳的修补和混乱的挣扎。

他苦笑着对队友说出了那句名言:

“看吧,这就是典型的——我花了10%10\%的时间想了个有问题的方案,无视复杂度和正确性匆忙上机,然后花了90%90\%的时间试图修复那10%10\%时间里写出的破代码。”

因此举,选手Y队伍三人丢掉了本该稳稳到手的参赛名额,选手Y也因此事写了一句名言告诫后人:

If you only 10% thinking, 90% trying to fix what you wrote in the first 10%.

现在,请输出这句名言来敲响警钟。

输入格式

无

输出格式

输出题目中的名言

样例

无输入
If you only 10% thinking, 90% trying to fix what you wrote in the first 10%.