?贪心算法，我也刚入门不久，个人总结了三个步骤
①：对应关系：找到题目中到底哪里使用了贪心
②：操作关系：怎么样的代码能够实现贪心的操作目的
③：终止关系：在什么情况下，贪心终止，也就是什么时候结束代码
这里首先需要注意的就是，当每次相加之后，产生的新一个数不一定是序列中最小的，也就是还得进行排序，此时选择排序的方法就尤为重要 .
没懂的xd，我也给出了图解/doge/
?
?对应关系
?由题目中就显而易见，每次选取的两个数一定是整个序列中去操作的，而对应关系，贪心的地方就是只需要每次挑选当前序列中最小的两个.
第一步，对应关系：发现想要让消耗的体力最小，则需要每次的操作结果都是最小，也就是每次都是整个序列中最小的两个进行相加.
?okk，接下来的比较简单的地方，直接上代码
?
int dui = 0; //多少堆果子(1<=n<=10000)
int tili = 0; //体力消耗量
int temp = 0; //交换量
printf("输入你的果子堆数:");
scanf("%d", &dui);
int *shu = (int *)malloc(sizeof(int)*dui);
printf("输入你每堆果子的重量:");
for (int i = 0; i < dui; i++)
{
scanf("%d", &shu[i]); //每堆数量(1<=shu[i]<=10000)
}
if(dui==1)
{
tili = shu[0];
}
for (int j = 0; j < dui; j++) //首先需要排一次升序
{
for (int k = 0; k < dui - j - 1; k++)
{
if (shu[k] > shu[k + 1])
{
temp = shu[k];
shu[k] = shu[k + 1];
shu[k + 1] = temp;
}
}
}
temp = 0; //为下一个交换重置??上面的变量创建我就不赘述了，接着往下
接下来是找到操作关系
不难发现只要我们在相加之后，进行简单的排序，然后就可以继续将两个最小的进行相加
那么，这道题中，两个数相加之后，在原有的数组上会少一个位置（搞不明白的去看我的Excel图解），然后我们要寻找方法，怎么去表示这个位置的变化，
我想到的方法就是，利用for循环，直接将相加结果放到两数相加的后一个元素的位置
然后体力+=后一个元素的结果值即可
?? ?for (int x = 0; x < dui-1; x++)
?? ?{
?? ??? ?shu[x + 1] = shu[x] + shu[x + 1];? ? ? ??? ?tili += shu[x+1];
?为什么这么操作？
x是不断往后的，而我只需要放到后面一个元素，就能保证在接下来的x++中，不会再与前一项有所牵连。
这是第一个操作关系
那么还有一个，就是排序
??? ??? ?for (int y =1; y < dui; y++)
?? ??? ?{
?? ??? ??? ?if (shu[y-1] > shu[y])
?? ??? ??? ?{
?? ??? ??? ??? ?temp = shu[y];
?? ??? ??? ??? ?shu[y] = shu[y-1];
?? ??? ??? ??? ?shu[y-1] = temp;
?? ??? ??? ?}
?? ??? ?}
?注意越界的问题，所以我直接用y为后一项，y-1为前一项来表示了.
我觉得也可以使用while还有冒泡排序，我这个似乎是交换了，欢迎大家贴出这两种方法的代码在评论区撒~
?终止关系
其实就是下面这几句
?? ?for (int x = 0; x < dui-1; x++)
?? ?{??? ???? ? ? ? ..............
? ? ? ?for (int y =1; y < dui; y++)
?? ??? ?{
?? ??? ??? ?if (shu[y-1] > shu[y])
最后附上我的运行图~
?
欢迎大家来访~
我是广州悠扬，一只奋发跟大佬步伐，并且励志成为优秀程序员的大一娃