2025 年第 24 题判断题动态规划提高
程序(二):删去去重语句是否影响输出
题目
阅读下面的程序,回答问题。 int n, k; int a[20000]; int ans[20007]; int main(){ scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); std::sort(a + 1, a + n + 1); n = std::unique(a + 1, a + n + 1) - a - 1; for (int i = 1, j = 0; i <= n; ++i) { for (; j < i && a[i] - a[j + 1] > k; ++j); ans[i] = ans[j] + 1; } printf("%d\n", ans[n]); } 判断题:将 n = std::unique(a+1, a+n+1) - a - 1; 这一行删去后,有可能出现与原本代码不同的输出结果。( 填 √ 或 × )
考点拆解
排序去重后用双指针维护分组
ans[i]=ans[j]+1 的递推含义:把元素按跨度不超过 k 贪心分组
易错提醒
判断删除某行代码是否影响结果时,要具体想清楚这行代码在整个算法里到底起什么作用,而不是凭直觉猜
阅读程序题要按变量变化顺序手推,不要跳步
选择题要检查单位、边界和题目中的否定词