题解 | #移动石头#

题目描述

有n堆石头排成一排，标号为0到n-1，第i堆石头有a[i]个石头
每一步你可以从某一堆取一个石头放到相邻的石头堆里
请问需要多少步可以将a数组变成b数组

输入描述:

第一行先输入一个整数n (1 ≤ n ≤ 50)
第二行输入n个数a_i 第三行输入n个数b_i 0 ≤ a_i, b_i ≤ 10⁶

输出描述:

输出一个整数表示最少的操作步数，如果无法将a数组变成b数组，输出-1

备注:

子任务1：n <= 10
子任务2：n <= 20
子任务3：无限制

思路：交换移动石头的顺序，并不会影响移动的步数。即最小步数可以通过依次将上一个石堆中多的石头数移到下一个石堆（或将下一个石堆中多的石头数移到上一个石堆）来实现。

代码如下：

#include<stdio.h>
#include<math.h>
int a[1000020],b[1000020];
int main(){
    long long int ans=0;
    int n,i,sum;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    for(i=0;i<n;i++) scanf("%d",&b[i]);
    for(i=0;i<n;i++){
        if(i==n-1){
            if(a[i]!=b[i]){
                printf("-1\n");
                return 0;
            }
        }
        sum=a[i]-b[i];
        ans+=abs(sum);
        a[i]-=sum;
        a[i+1]+=sum;
    }
    printf("%lld\n",ans);
    return 0;
}