贪心算法(算法复习)
2021/11/12 22:41:40
本文主要是介绍贪心算法(算法复习),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.跳跳
描述
你是一只小跳蛙,你特别擅长在各种地方跳来跳去。
这一天,你和朋友小 F 一起出去玩耍的时候,遇到了一堆高矮不同的石头,其中第 i 块的石头高度为 hi,地面的高度是 h0=0。你估计着,从第 i 块石头跳到第 j 块石头上耗费的体力值为 (hi-hj)^2,从地面跳到第 i 块石头耗费的体力值是 (hi)^2
为了给小 F 展现你超级跳的本领,你决定跳到每个石头上各一次,并最终停在任意一块石头上,并且小跳蛙想耗费尽可能多的体力值。
当然,你只是一只小跳蛙,你只会跳,不知道怎么跳才能让本领更充分地展现。
不过你有救啦!小 F 给你递来了一个写着 AK 的电脑,你可以使用计算机程序帮你解决这个问题,万能的计算机会告诉你怎么跳。
那就请你——会写代码的小跳蛙——写下这个程序。
输入
输入一行一个正整数 n,表示石头个数。
输入第二行 n 个正整数,表示第 i 块石头的高度 hi。
输出
输出一行一个正整数,表示你可以耗费的体力值的最大值。
样例输入
2
2 1
3
6 3 5
样例输出
5
49
#include<iostream> #include<cmath> #include<algorithm> using namespace std; int main(){ int a[333]; int n,h=0; cin>>n; a[0]=0; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a,a+n+1); int i=0,j=n; while(i<j){ h+=pow(a[i]-a[j],2); i++; h+=pow(a[i]-a[j],2); j--; } cout<<h; return 0; }
2.
描述
给出n个正整数,将他们排成一排组成一个最大的正整数。
n=3
13 342 313
34231313
n=4
7 23 567 8
8756723
设计解决这一问题的贪心策略。
#include<iostream> #include<algorithm> #include<string> using namespace std; /*最大*/ bool cmp1(string a,string b){ return a+b>b+a; } /*最小*/ bool cmp2(string a,string b){ return a+b<b+a; } int main(){ string a[100000]; int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n,cmp1); cout<<"Max="; for(int i=0;i<n;i++){ cout<<a[i]; } sort(a,a+n,cmp2); cout<<"\tMin="; for(int i=0;i<n;i++){ cout<<a[i]; } return 0; }
这篇关于贪心算法(算法复习)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)