列表

详情


NC21740. 移动石头

描述

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

输入描述

第一行先输入一个整数n (1 ≤ ≤ 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

输入:

3
0 0 1
1 0 0

输出:

2

示例4

输入:

9
3 10 0 4 0 0 0 1 0
5 5 0 7 0 0 0 0 1

输出:

9

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2023-02-07 09:51:31

#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;
}

C 解法, 执行用时: 2ms, 内存消耗: 496K, 提交时间: 2022-11-09 15:39:07

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

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 444K, 提交时间: 2022-11-09 16:30:10

#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,n,a[51]={0},b[51]={0},cnt=0;
	cin>>n;
	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];cnt+=abs(a[i]-b[i]);
	}
	if(a[n]==b[n]){
		cout<<cnt;
	}
	else{
		cout<<-1;
	}
	return 0;
	
}

Python3 解法, 执行用时: 42ms, 内存消耗: 4592K, 提交时间: 2023-05-18 15:01:48

n,a,b=int(input()),list(map(int,input().split())),list(map(int,input().split()))
for i in range(n-1):
    a[i+1]+=a[i]
    b[i+1]+=b[i]
print(-1 if a[-1]!=b[-1]else sum(abs(a[i]-b[i]) for i in range(n)))

上一题