有一段代码，共有n行，起初第i行代码的开头有 𝑎 𝑖 a i ​ 个空格，根据代码的逻辑关系，小爱希望第i行开头调整成为 𝑏 𝑖 b i ​ 个空格。 小爱的文本编辑器有一个功能，它可以选中任意多行连续的代码，通过一步操作就可以在这些行的开头增加或删除一个空格。注意，若选择删除一个行首空格，必须保证选中的每一行行首都至少有一个空格，不然文本编辑器会误删其他字符，程序就要出错了。 请问最少需要多少步，才能让这段代码的缩进调整成指定的样子？ 输入格式 第一行：单个整数 𝑛 n； 第二行到第 𝑛 + 1 n+1行：每行两个整数，表示 𝑎 𝑖 a i ​ ​与 𝑏 𝑖 b i ​ ​； 输出格式 单个整数：表示最少步数。(差分）

要解决这个问题，我们可以使用差分数组的思想。具体来说，我们可以通过维护一个累积的变化量来计算最小的操作次数。下面是详细的解决方案： ### 解决方案步骤 1. **初始化**：创建一个 `steps` 变量用于记录总的操作步数，并且准备两个辅助数组来存储原空格数量和目标空格数量。 2. **遍历每一行**：对于每一个给定的 `(ai, bi)` 对，我们需要确定如何从 `ai` 变为 `bi`。这可以通过以下两种方式进行： - 如果 `ai < bi`，则需要在这几行前面添加若干个空格； - 如果 `ai > bi`，则需要删除多余的空格。 3. **使用差分数组优化**：为了高效地处理连续区间上的增量操作（即同时对多行进行相同的操作），我们可以用到“差分”思想。引入一个新的数组 `diffs[]` 来追踪每个位置处所需的净变化值。每当遇到一对 (start,end) 需要在[start...end]范围内做统一修改时，在 `diffs[start] += changeValue; diffs[end + 1] -=changeValue`. 4. **累计计算最终结果**：遍历整个文件并应用上述规则后，检查当前行是否达到了预期的目标状态。如果某一行已经满足条件，则不需要额外动作；否则更新 `steps` 并相应调整后续影响范围内的元素。 5. **输出答案**：将得到的结果输出即可。 ### C++ 实现代码如下： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n), b(n); for(int i = 0; i < n; ++i){ cin >> a[i] >> b[i]; } // 差分数组法 vector<long long> changes(2 * n); // 辅助空间足够大以避免越界 for(int i = 0; i < n; ++i){ if(a[i] != b[i]){ int diff = b[i] - a[i]; // 计算该行所需改变的数量 // 更新差分表 changes[abs(diff)]++; // 开始位置加一 changes[n + abs(diff)]--; // 结束位置减去之前加上的一次 } } long long steps = 0; long long sum = 0; for(int i = 0; i <= n; ++i){ // 注意这里只迭代到n就够了因为超过部分都是无效区间的标记了 sum += changes[i]; // 维护当前位置实际的影响次数 if(sum > 0){ steps++; sum--; } else if (sum < 0){ steps -= sum; sum = 0; } // 把所有已处理过的前缀清零确保不会重复计数 while(i < changes.size() && changes[i] == 0) i++; --i; // 因为我们手动递增了一次所以恢复回来 } cout << steps << endl; return 0; } ``` 请注意这个算法假设输入数据合法有效并且没有边界情况如全部相等的情况直接返回0步也可以考虑特判一下提高鲁棒性。 ### 提供更简洁版本理解思路: 考虑到每一段连续的不同缩进区域只需要一次操作就能完成转换而无需关心具体的数值差距大小因此可以进一步简化为统计不同连通块数目然后得出结论。 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; const int MAXN=1e6+7; ll N,a[MAXN],b[MAXN]; bool check(ll x,ll y){ return abs(x-y)>0; } signed main(){ cin>>N; for(ll i=1;i<=N;++i) scanf("%lld%lld",&a[i],&b[i]); ll ans=0,last=-1; for(ll i=1;i<=N;++i){ if(check(a[i],b[i])){ if(last==-1||!check(a[last],b[last]))ans++,last=i; }else last=-1; } cout<<ans<<"\n"; return 0; } ``` 此代码实现了基于连贯区块概念下的最优解求取过程。 ### 原因分析 本题核心在于利用数学建模的方式寻找最简路径从而减少不必要的复杂度。通过识别出各个独立的、不可分割的任务单元（此处表现为相邻但非一致的缩进级别转变）之后再逐项累加以获得全局最低成本的方法是常见的一种贪心策略体现形式之一。