蓝桥杯算法提高-能量项链-题解(C++代码)（思路简单）

4792 阅读 18 评论 0 点赞

### 解题思路
我以前写得怎么这么抽象啊，这都是啥啊，好羞耻，改了

求最大能量的方法是先把小的数字吞了，然后剩下的都是大数字
一共要吞n-1次，每次都求当前最小的数字然后吞掉（这大概就是 贪心算法）
比如2,4,3,6,5
能量最大的连接方式：
5-2-4————40
4-3-6————72
5-4-6————120
6-5-6————180
总能量412
注意中间的数字，会发现他们在本次数组里都是最小值。
大概像下面这样
![](/image_editor_upload/20210519104433_61949.png)
被吞掉的珠子在数组A里就直接置0，检查的时候检查到0就跳过，往前或者往后移一位。

### 参考代码

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
//最多也就100个珠子，那最大值设为105
int a[105];
int b[105];

int main(){
    int n,sum = 0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i] = a[i];
    }
    //stl库的排序，给B数组排个序
    sort(b,b+n);

//有n个珠子，就要合成n-1次
    for(int k = 0;k<n-1;k++){
        int index;
        for(index = 0;index < n;index++)
            if(a[index] == b[k])
                break;
        /*
        *如上我们找到了目前最小的珠子的下标
        *那就找他前面的下标pre和后面的下标next
        */
        int pre=index - 1,next = index + 1;
        //前驱已经被吞掉的情况和前驱小于0的情况
        while(a[pre] == -1 || pre<0){
            if(pre<0)
                pre = n-1;
            else
                --pre;
        }
        //后继已经被吞掉的情况和后继大于最大下标的情况
        while(a[next] == -1 || next >= n ){
            if(next >=n )
                next = 0;
            else
                ++next;
        }
        //算能量
        sum = sum + a[pre] * a[index] * a[next];
        a[index] = -1;//中间的珠子被消灭了

}
    cout<<sum<<endl;
    return 0;
}

```
```
然后注意有顺序要求，2 3 5 10 和2 5 3 10得出的结果是不一样的
![](/image_editor_upload/20210519104912_86775.png)
![](/image_editor_upload/20210519104943_60127.png)

0.0分

33 人评分

本文分类：题解列表
浏览次数：4792 次浏览
发布日期：2019-12-14 00:34:24
本文链接：https://blog.dotcpp.com/a/63856

上一篇 > 41.输出全排列-题解(C++代码)
下一篇 > Kanna-邮票组合问题*--C

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 18 条评论

e^πi+1=0 4年前回复TA

这答案直接错了吧

danny 4年前回复TA

好像不对吧@-@

萌新一大只 4年前回复TA

为什么输入4
2 5 3 10出来不是710呢

木子CoCo~ 4年前回复TA

详细

汝顾 4年前回复TA

@汝顾 emmm，看到了，刚才没注意

汝顾 4年前回复TA

楼主，你数组排序，for循环少写了个括号吧

汝顾 4年前回复TA

@未来定是全能超 因为吞并的数是从小到大的，所以求出的结果也就是最大的

未来定是全能超 4年前回复TA

请教一下为什么这样算出来就是最大的呢？

蓝桥杯算法提高-能量项链-题解(C++代码)（思路简单）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 18 条评论

发表评论 取消回复

评论列表共有 18 条评论

发表评论取消回复