相对比较简单
T1 编辑距离
T2
题意:已知 \(1 <= n,x<=1e6\) ,你确定一个数\(v\),按顺序给出 \(n\) 个数\(a_i\),当\(|a_i-v|<=x\)时这个\(a_i\)记为OK,否则你就需要给v再指定一个值满足之前的条件。
请问最少需要变动多少次v的值才能使得所有\(a_i\)为OK
思路:
记录\(a_i\)最大最小值,超过\(2 \cdot x\)就要改变\(v\)的值
int l = -1, r = -1, ans = 0;
for(int i = 1; i <= n; i++){
int tmp;
scanf("%d", &tmp);
if(l == -1)l = r = tmp;
l = min(l, tmp), r = min(r, tmp);
if(r - l > 2 * x){
ans++;
r = l = tmp;
}
}
printf("%d", ans)