题解：P15980 [PA 2026] 买砾石 / Dostawa żwiru

Accepted_MAXN · 2026-03-30 20:01:06 · 题解

蒟蒻的第一篇题解，管理员求过。

原题 & 更好的阅读体验

思路

没什么好说的，模拟即可，但要注意，不能： ::::error[错误思路示范]

• 只遍历一次，判断差是否大于 k 然后累加，最后输出答案，如下面这样：

  #include<bits/stdc++.h>
  using namespace std;
  int n,k,a[1005],ans;
  int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        if(abs(a[i]-a[i+1])>k){
            while(abs(a[i]-a[i+1])>k){
                ans++;
                if(a[i]<a[i+1])a[i]++;
                else a[i+1]++;
            }
        }
    }
    cout<<ans;
    return 0;
  }

  这样只会爆 \color{red}0，因为假如你当前改了这一段路的高度，可能前一段路又不满足条件了，如下面这组样例能证明：

  
  输入：
  3 1
  2 3 6

输出： 2

过程：
先判断 $2$ 和 $3$，发现差值等于 $k$，满足跳过，然后判断 $3$ 和 $6$，最小修改次数为将 $3$ 改为 $5$，加 $2$，最后序列为：

2 5 6

显然，第一组 $2$ 和 $5$ 不满足条件，所以这个思路是错误的。
::::
::::success[正确思路 & AC code]{open}
正确思路是一直不停循环，先判断如果上一轮循环有修改，那就继续循环，否则终止循环，输出答案。每次循环遍历整个序列，判断每两段街道是否符合条件，并且每次循环定义一个变量为 $0$，如果这次循环有修改，就将其改为 $1$，不符合就修改再累加次数。
## code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005];
long long ans;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    bool c=1;
    while(c){
        c=0;
        for(int i=1;i<n;i++){
            int d=abs(a[i]-a[i+1]);
            if(d>k){
                c=1;
                int e=d-k;
                ans+=e;
                if(a[i]>a[i+1])a[i+1]+=e;
                else a[i]+=e;
            }
        }
    }
    cout<<ans;
    return 0;
}