首页 > 试题广场 >

石子合并

[编程题]石子合并

热度指数：4028 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小Q和牛博士在玩一个石子合并的游戏，初始一共有n堆石子，每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并，每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆，这次合并得分为x*y，当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分，希望你能来帮他们算算最大得分多少。

输入描述:

输入包括两行，第一行一个正整数n(2≤n≤100)。

第二行包括n个正整数w[i](1≤w[i]≤100)，即每堆石子的个数。

输出描述:

输出一个正整数，即小Q和牛博士最大得分是多少。

示例1

输入

3
1 2 3

输出

算法知识视频讲解

pein531

没有用什么高超诡谲的技巧，直接用栈这个数据结构来做的。将所有的石子都压入栈中，然后每次弹出栈顶的两堆石子进行合并，合并结果再压入栈中，重复这一过程直到栈中只剩下一堆石子。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strStone = br.readLine().trim().split(" ");
        int score = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++)
            stack.push(Integer.parseInt(strStone[i]));
        // 直接对栈顶的两堆石子弹出进行合并，合并结果再压入站中，重复这一过程直至栈中只有一堆石子
        while(stack.size() > 1){
            int num1 = stack.pop();
            int num2 = stack.pop();
            score += num1*num2;
            stack.push(num1 + num2);
        }
        System.out.println(score);
    }
}

发表于 2021-02-06 11:41:40 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,w[101],res=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>w[i];
    sort(w,w+n);
    for(int i=n-1;i>0;i--)
    {
        res=res+w[i]*w[i-1];
        w[i-1]=w[i]+w[i-1];
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-06-27 11:13:13 回复(0)

呼叫-鲸鱼船长

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d\n",&n);
    int w[100];
    int i;
    for(i = 0;i < n;i++)
    {
        scanf("%d ",&w[i]);
    }
    int b[100];
    int score[100];
    b[0] = w[0] + w[1];
    score[0] = w[0]*w[1];
    for(i = 1;i < n-1;i++)
    {
        b[i] = b[i-1] +w[i+1];
        score[i] = score[i-1] + b[i-1]*w[i+1];
    }
    printf("%d\n",score[n-2]);
    return 0;
}

发表于 2019-04-09 19:29:19 回复(0)

Java

ZLMing

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int sum = 0;
        int num = arr[0];
        for(int i=1;i<n;i++){
            sum = sum+arr[i]*num;
            num = num + arr[i];
        }
        System.out.println(sum);
    }
}

发表于 2019-01-15 18:38:40 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main(){  int n,x,y; 
    while(cin>>n)  {
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i=0;i<n;i++)  {
            cin>>x;
            q.push(x);
        }  int s = 0;
        while(q.size()>1)  {
            x = q.top();
            q.pop();
            y = q.top();
            q.pop();
            s += x*y;
            q.push(x+y);
        }
        cout<<s<<endl;
    }
    return 0;
}

编辑于 2020-03-09 23:12:09 回复(1)

Dr.A.Clef

#include <iostream>

using namespace std;

int main() {
    int n; cin >> n;
    int stock = 0, score = 0;
    for(int curr; cin >> curr; ) {
        score += stock * curr;
        stock += curr;
    }
    cout << score;
}

其实顺序完全不影响的。无论什么顺序都是一样的结果。

设w1,w2,...,wn是一个任意的合并顺序（即先取w1，之后w1和w2合并，再之后w1 + w2,w3合并……）
在该合并顺序下的得分为：
$图片说明$
将上面的式子乘以二，再将含有w1,w2,...wn的项提出来（把下面的和上面的对比你会发现每一个都多用了一遍），得到：
$w_1(w_2+w_3+w_4+\ldots+w_n)+\\ w_2(w_1+w_3+w_4+\ldots+w_n)+\\ \ldots+\\ w_k(w_1+\ldots+w_{k-1}+w_{k+1}+\ldots+w_n)+\\ \ldots+\\ w_n(w_1+w_2+w_3+\ldots+w_{n-1})$
记 $S_n=\sum_{i=1}^nw_i$ ，那么其实总得分就是 $图片说明$ ，与具体序列的顺序无关，只与序列元素的值有关。

编辑于 2019-03-08 16:57:04 回复(3)

向宇回桌

不是很理解那些要排序的答案，我用数归证了，合并次序不影响结果呀。

import java.util.*;

public class Main {
    private static final int MAX = 105;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[MAX];
        for (int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }
        int ans = 0, cur = arr[1];
        for (int i=2; i<=n; i++) {
            ans += cur * arr[i];
            cur += arr[i];
        }
        System.out.println(ans);
        return;
    }
}

编辑于 2019-02-11 15:42:05 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&arr[i])
    }
    sort.Ints(arr)
    ans:=0
    for len(arr)>1{
        x,y:=arr[len(arr)-2],arr[len(arr)-1]
        ans+=x*y
        arr=append(arr[:len(arr)-2],x+y)
    }
    fmt.Print(ans)
}

发表于 2023-03-19 08:16:25 回复(0)

Python

牛客817844335号

n = int(input())
w = list(map(int,input().split(' ')))
score = 0
while True:
if len(w) == 1:
break
else:
w = sorted(w,reverse=True)
l_1 = w.pop(-1)
l_2 = w.pop(-1)
score += l_1*l_2
w.append(l_1+l_2)
print(score)

编辑于 2020-09-06 17:31:09 回复(0)

dingsong

import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] w=new int[n];
for(int i=0;i<n;i++){
w[i]=sc.nextInt();
}
int grade=0;

for(int i=0;i<n-1;i++){
grade+=w[i]*w[i+1];
w[i+1]=w[i]+w[i+1];
}
System.out.print(grade);
}
}

发表于 2020-08-23 11:16:33 回复(0)

牛客142107967号

两两乘积求和就完事了，为毛要排序？
n=int(input())
w=[int(i) for i in raw_input().split(' ')]
s=0
for i in range(n-1):
    for j in range(i+1,n):
        s+=w[i]*w[j]
print s

发表于 2020-07-29 13:51:03 回复(0)

Python

wangkss_01

原来这个题没必要排序的。。。

说下我思路，不是最优的，但算是一种方法：

1.首先要想分数最高，那么对大的堆一定要用很多次，作为多次因子；

2.另外考虑到递归，就是F(k₁,k₂,...,k_n) = k_n*（k₁+k₂+...+k_n-1）+ F(k₁,k₂,...,k_n-1)，其中k₁,k₂,...,k_n是从小到大排序的。

发表于 2020-06-13 22:23:51 回复(0)

C/C++

海问香12138

#include <stdio.h>
#include <stdlib.h>

#define MAXN 101

long long n;
long long a[MAXN];

int cmp(const void* a,const void* b);	//´Ó´óµ½Ð¡ 

int main()
{
	long long i,sum=0;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
		scanf("%lld",a+i);
	qsort(a,n,sizeof(a[0]),cmp);
	for(i=1;i<n;i++)
	{
		sum += a[i] * a[i-1];
		a[i] += a[i-1];
	}
	printf("%lld\n",sum);
	return 0;
}

int cmp(const void* a,const void* b)
{
	return *(int *)b - *(int *)a;
}

发表于 2019-08-19 10:10:23 回复(0)

Yasin_

n = int(input())
nums = [int(num) for num in input().split()]
nums.sort()
score = 0
tmp = nums[0]
for i in range(1, n):
    score += nums[i] * tmp  # 将tmp当做x 将nums[i]当做y
    tmp = nums[i] + tmp
print(score)

编辑于 2019-08-01 16:35:18 回复(0)

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        inp=list(map(int,input().strip().split(' ')))
        #print(inp)
        inp=sorted(inp)
        list1=[]
        while len(inp)!=1:
            sum1=inp[-1]+inp[-2]
            mul=inp[-1]*inp[-2]
            list1.append(mul)
            inp=inp[:-2]+[sum1]
        #print(list1)
        result=sum(list1)
        print(result)
    except:
        break

发表于 2019-07-24 09:28:02 回复(0)

Python

灵鹫听经

定义一个函数，函数每次先排序w，然后遍历，找到最相近的两个数，更新得分，在w后添加两数的和，并在原列表中删除两数。上述过程做完后，不用等遍历结束即可推出（另外；定义函数中找最相近两数时，也是一个遍历过程，循环从0到w的极差）反复调用函数，每次调用都会合并两个数，即w长度减一，w的长度为1时即可推出循环；

# 获取输入的数据 n = int(input())
w = list(map(int, input().split())) # 初始化得分为0 score = 0   def cross(w, score): """  定义一个函数，每次调用都会合并w中最接近的两项    :param w:    :param score:    :return:  """    # if n == 1:  #     return w, score  # 对w的预处理，排序；使得最相近的两数相邻    w = sorted(w)  # 求w的极差    gap = max(w)-min(w)  # 寻找最相邻的两数也是一个遍历过程，可能的取值从0到极差    for i in range(gap+1):  # 从头遍历w中的 每个元素，看它与它的前一项是否符合本轮要找的最相近的两数    for j in range(1, len(w)):  if w[j]-w[j-1] == i:  # 当找到最相邻的两数时，更新得分    score += w[j]*w[j-1]  # w得到两数合并之后的新的成员    w.append(w[j] + w[j - 1])  # 除去旧的成员  w.pop(j)
                  w.pop(j-1)     # 只要找到就可以直接推出循环，返回新的w与更新过的score    return w, score while True: # 多次调用函数，直到w长度为1时，推出循环    if len(w) == 1:  break  else:
          w, score = cross(w, score) print(score)

编辑于 2019-07-17 10:31:36 回复(0)

OPPO学长

#include <iostream>
using namespace std;

int main()
{
    int n,stone;
    cin>>n;

    int sum=0,score=0;
    for(int i=0; i<n; i++)
    {
        cin>>stone;
        score+=sum*stone;
        sum+=stone;

    }
    cout<<score<<endl;


    return 0;
}

还是不懂为啥不用排序。虽然排序确实不影响结果。。。。

发表于 2019-04-08 17:13:47 回复(0)

一生白色

amount = int(input())
w = list(map(int,input().split()))
Sum = 0

for i in range(amount-1):
    for j in range(i+1, amount):
        Sum += w[i] * w[j]
print(Sum)

这道题推了一下，发现得分和归并的顺序无关····笛卡尔积去掉w(i,i)再相加即可

编辑于 2019-04-07 01:50:28 回复(0)

yvettre

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> w(n,0);
    for (int i=0;i<n;i++) cin>>w[i];

    int res = 0;
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            res = res + w[i]*w[j];
        }
    }
    cout<<res<<endl;
}

发表于 2019-03-10 16:31:11 回复(0)

Python

体重不增到120不改名

先排序，想要得分最高，每次都选数量最多的两个堆，这个在数学上可以证明。

n=int(input())
L=list(map(int,input().split()))
L.sort()
s=0
for i in range(n-1):
    t=L.pop()
    s+=(t*L[-1])
    L[-1]+=t
print(s)

发表于 2019-03-09 16:44:56 回复(0)

提交观点

问题信息

上传者：小小

难度：

23条回答 15收藏 5526浏览

通过挑战的用户

查看代码

在查重的螺狮粉很刻苦

2022-09-25 20:23:04
牛客44030...

2022-09-13 07:32:36
牛客70437...

2022-09-08 22:31:51
2023继续找工作

2022-09-08 20:10:50
ChaoYou...

2022-09-07 11:17:41

石子合并

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题