csppass
连续 00 XP登录 / 注册
202527阅读程序动态规划提高

程序(二):误删排序语句可能出现的问题

题目

阅读下面的程序,回答问题。 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]); } 假设输入的 a 数组和 k 均为正整数,但 a 数组不一定有序,若误删去 std::sort(a+1, a+n+1); 这一行,程序有可能出现的问题有( )

考点拆解
排序去重后用双指针维护分组
ans[i]=ans[j]+1 的递推含义:把元素按跨度不超过 k 贪心分组
易错提醒
阅读程序题要按变量变化顺序手推,不要跳步
选择题要检查单位、边界和题目中的否定词