题目内容:

image-20210314200115335

题目分析:

这道题可以用贪心做,局部最优解很明显。

题目说了,每跳一次,消耗的体力值是两个石头高度差的平方,地面高度为0。可以在任意两个石头之间跳,最终每个石头各跳一次,要求所消耗的体力值最多。

因为题目已说明,每次跳消耗的体力是高度差的平方,那么就是从高跳到低与从低跳到高一样。因为要求每个石头各跳一次,那么跳的总次数是固定的。所以要求最终消耗的体力值最多,那么就是说要每次消耗的体力值尽可能大,这就是这道题的基本贪心思路。怎么做才能尽可能的大?当然是高度差越高越好。

分析到这些这道题就很简单了,就是每次跳的高度差越大越好,就是每次从没跳过的石头里面从最低的跳到最高的上面,或者从最高的跳到最低的上面,跳过之后排除这个石头,循环执行这个操作,直至所有的石头都跳过一次。

具体的代码实现,可以使用双指针的对撞指针,排序后从数组两端开始,一高一低,依次遍历直至所有数均使用过一次。也可循环遍历数组中的最大最小值,在没使用过的两个最值之间跳,使用过后从数组中移除,直至数组为空。

另外,这道题注意保存体力值的变量要开long long,否则有些样例的结果用int可能存不下。

这里我用的是最值的方法做的,因为这是最直观的方法,也是最先想到了。

具体代码:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;


int main() {
int n,x,mf=1,f=0;
long long sum=0;
cin>>n;
list<int> num;
for(int i=1;i<=n;i++) {
cin >> x;
num.push_back(x);
}
while(!num.empty()){
if(mf==1) {
int maxNum = *max_element(num.begin(), num.end());
sum += (maxNum - f) * (maxNum - f);
f = maxNum;
num.remove(maxNum);
mf=0;
}else{
int minNum=*min_element(num.begin(),num.end());
sum+=(minNum-f)*(minNum-f);
f=minNum;
num.remove(minNum);
mf=1;
}
}
cout<<sum<<endl;
return 0;
}