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; }