admin 管理员组

文章数量: 1087139

洛谷

跳跳！ - 洛谷

解题思路：

1.由题意得，要求所耗费的体力最大值，体力值的计算 公式给出，可以判断，两个石头的高度差越大即越 好，所以这里的贪心思想是总要跳到和当前石头高度 差最大的那个石头

2. 利用数组将n个石头的高度存储后，每一轮是要找到那 个高度差最大的石头

3. 第一轮是从地面上跳到石头1，设置一个书签temp= 0，这里表示在地面上，遍历数组找到和temp高度差最 大的那个数以及在数组中编号num，计算耗费的体力 值，sum=sum+(a[num)-temp)^2,将书签设置为当前石头 的高度temp=a[num]，并将这个石头所在的编号标记已 经跳过的石头，a[num]=-1,下一次再遍历的时候不再判 断，然后接着跳第二个石头，一共是跳n次

4. 输出体力值，在这里sum为longlong型，防止数据溢出

#include<bits/stdc++.h>
using namespace std;
long long sum;//计算耗费的体力值
int a[305]; 
int main()
{int n,num;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//输入n个石块的高度 int temp=0,k=n;while(k--)//表示一共要跳n次 {int max=0; for(int i=1;i<=n;i++)//遍历整个数组 {if(a[i]!=-1)//如果当前石头还没跳过 {if((a[i]-temp)*(a[i]-temp)>max){max=(a[i]-temp)*(a[i]-temp);num=i;}}}//找到跳到下一个石头耗费体力值最大的编号为num sum=sum+(a[num]-temp)*(a[num]-temp);//累加体力值 temp=a[num];//将当前所在的石头高度赋值给temp a[num]=-1;//将当前石头标记为已经跳过 }cout<<sum; return 0;
}

解题思路2：

1.如果是要求浪费体力值最大的，那么可以想到首先跳到最高的地方，然后跳到最低的，接着继续跳到没有跳过的最高的，继续跳到没有跳过的最低的

2.设置两个书签，并且复制一个数组b，和a相同，（其实可以不复制，更加形象），从数组b为flag1=1开始逐渐递增，数组b为flag2=n开始逐渐递减

3.每次跳两个台阶，直到所有台阶都跳完，结束循环

#include<bits/stdc++.h>
using namespace std;
int a[310],b[310];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//输入数组a sort(a+1,a+n+1);//对a进行升序排序 for(int i=1;i<n;i++)//将数组a复制给数组b b[i]=a[i];long long sum=a[n]*a[n];//sum表示跳到第一个最高的台阶上浪费的体力 int flag1=1,flag2=n,num=1;//flag1表示数组b的书签，flag2表示数组a的标签,num统计数量while(1){sum=sum+(a[flag2]-b[flag1])*(a[flag2]-b[flag1]);//累加从最高跳到最低 flag2--;//书签减1，表示没有跳过中最高的 sum=sum+(a[flag2]-b[flag1])*(a[flag2]-b[flag1]);//累加最低跳到最高 flag1++;//书签加1，表示没有跳过中最低的 num=num+2;//跳的台阶数量加2 if(num>=n){break;}}cout<<sum;return 0;
}

本文标签： 洛谷

版权声明：本文标题：洛谷 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1693679377a236392.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。