NC207202. 移动石头
描述
有n堆石头排成一排,标号为0到n-1,第i堆石头有a[i]个石头
每一步你可以从某一堆取一个石头放到相邻的石头堆里
请问需要多少步可以将a数组变成b数组
输入描述
第一行先输入一个整数n (1 ≤ n≤ 50)
第二行输入n个数ai
第三行输入n个数bi
0 ≤ ai, bi ≤ 106
输出描述
输出一个整数表示最少的操作步数,如果无法将a数组变成b数组,输出-1
示例1
输入:
2 1 2 2 1
输出:
1
示例2
输入:
2 10 0 0 10
输出:
10
示例3
输入:
10 1 2 3 4 5 6 7 8 9 10 8 5 4 7 9 6 3 2 1 4
输出:
-1
Java(javac 1.8) 解法, 执行用时: 51ms, 内存消耗: 12120K, 提交时间: 2020-06-03 15:16:33
import java.util.Scanner; public class Main { public static void main(String[] args) { int n,mun=0; int a[] = new int[100],b[]=new int[100]; Scanner sc = new Scanner(System.in); while(sc.hasNext()) { n = sc.nextInt(); int sum1=0,sum2=0; for(int i=0;i<n;i++){ a[i] = sc.nextInt();; sum1+=a[i]; } for(int i=0;i<n;i++){ b[i]=sc.nextInt();; sum2+=b[i]; } if(sum1!=sum2){ System.out.print(-1); } else{ for(int i=0;i<n-1;i++){ a[i+1]+=a[i]-b[i]; mun+=Math.abs(a[i]-b[i]); } System.out.print(mun); } } } }
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2020-06-03 15:28:05
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int n,a[100],b[100],mun=0; int main() { cin>>n; int sum1=0,sum2=0; for(int i=0;i<n;i++){ cin>>a[i]; sum1+=a[i]; } for(int i=0;i<n;i++){ cin>>b[i]; sum2+=b[i]; } if(sum1!=sum2){ cout<<-1<<endl; } else{ for(int i=0;i<n-1;i++){ a[i+1]+=a[i]-b[i]; mun+=abs(a[i]-b[i]); } cout<<mun<<endl; } return 0; }
Python3(3.5.2) 解法, 执行用时: 54ms, 内存消耗: 3452K, 提交时间: 2020-06-03 15:45:59
n = int(input()) a = [int(i) for i in input().split()] b = [int(i) for i in input().split()] if sum(a) != sum(b): print(-1) else: count = 0 for i in range(n - 1): if a[i] < b[i]: num = b[i] - a[i] a[i + 1] -= num count += num else: num = a[i] - b[i] a[i + 1] += num count += num print(count)
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2022-10-31 22:59:20
#include<bits/stdc++.h> using namespace std; int main() { int n; int a[51]={0}; int b[51]={0}; cin>>n; long long int ans=0; for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1]; for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1],ans+=abs(a[i]-b[i]); if(b[n]!=a[n]) cout<<-1; else cout<<ans; }