列表

详情


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

上一题