跳转至

P1052 [NOIP2005 提高组] 过河

  • l很大，但障碍物数量很小，可以缩小两障碍物之间的距离，类似离散化
  • 注意这种优化的前提是 \(s\neq t\) ,需要特判
  • 注意缩小后相邻障碍物距离应小于 t(t-1)

错误：

  • 可能在处理之前pos[i]-pos[i-1]比t(t-1)小，但pos[i-1]先被处理，变得很小，拉开了pos[i]和pos[i-1]的距离，使优化后pos[i]和pos[i-1]的距离变为t(t-1)
1
2
3
4
for(int i = 1; i <= m; i++){
    cin >> pos[i];
    if(pos[i] - pos[i - 1] > t * (t + 1)) pos[i] = pos[i - 1] + t * (t - 1);
}

正确：

1
2
3
4
5
6
7
sort(pos + 1, pos + 1 + m);
for(int i = 1; i <= m; i++){
    diff[i] = min(pos[i] - pos[i - 1], t * (t - 1));
}
for(int i = 1; i <= m; i++){
    pos[i] = pos[i - 1] + diff[i];
}
  • 关注题目输入数据是否有序!
1
sort(pos + 1, pos + 1 + m);