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

程序(二):n=100,k=2,a={1..100} 时的输出

题目

阅读下面的程序,回答问题。 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=100、k=2、a={1,2,...,100} 时,输出为( )

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