有一个游戏，玩法是在一堆长度不一的小棍中找出三根棍子，拼出一个周长最大的三角形。有什么策略能快速的找到三根小棍么？
请你来试试吧
输入格式:
在一行中给出小棍的个数 N，另一行中分别给出 N 个小棍的长度，之间用空格隔开。
输出格式:
如果小棍的数量小于 3，则输出小棍的个数不能组成三角形；如果找到最大的三角形，则输出最大三角形的周长是?，并在下一行中输出组成最大三角形的三条边是?,?,?，三条边之间用英文逗号隔开并从小到大输出；如果没有找到，则输出没有找到能组成三角形的小棍。
输入样例1:
1
2
| 10
233 120 747 75 67 336 221 845 780 403
|
输出样例1:
1
2
| 最大三角形的周长是2372
组成最大三角形的三条边是747,780,845
|
输入样例2:
输出样例2:
输入样例3:
输出样例3:
1
2
3
| 代码长度限制 16 KB
时间限制 30 ms
内存限制 64 MB
|
代码演示:
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
34
35
36
37
38
39
40
41
42
| import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n<3){
System.out.println("小棍的个数不能组成三角形");
}
Scanner sc1 = new Scanner(System.in);
String sr = sc1.nextLine();
String arr1[] = sr.split(" ");
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(arr1[i]);
}
getLongestTriangle(arr);
}
public static int getLongestTriangle(int[] arr) {
if (arr == null || arr.length < 3) {
return 0;
}
Arrays.sort(arr);
for (int i = arr.length - 1; i >= 2; i--) {
int longEdge = arr[i];
int midEdge = arr[i - 1];
int shortEdge = arr[i - 2];
if (midEdge + shortEdge > longEdge) {
System.out.print("最大三角形的周长是");
System.out.println(midEdge+shortEdge+longEdge);
System.out.println("组成最大三角形的三条边是"+shortEdge+","+midEdge+","+longEdge);
return longEdge + midEdge + shortEdge;
}else if ((!(midEdge + shortEdge > longEdge))){
System.out.println("没有找到能组成三角形的小棍");
}
}
return 0;
}
}
|
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
34
35
36
| #include<stdio.h>
int main(){
int n = 0;
if(scanf("%d",&n)){}
int arr[n];
int i = 0;
for(;i<n;i++){
if(scanf("%d",&arr[i])){}
}
if(n<3){
printf("小棍的个数不能组成三角形\n");
return 0;
}else{
for(i=1;i<n;i++){
int j = i-1;
int t = arr[i];
while(j >= 0 && arr[j] > t){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = t;
}
for(i=n-1; i>=0; i--) {
if(i<n-3) {
printf("没有找到能组成三角形的小棍");
break;
}
if(arr[i-1]+arr[i-2]>arr[i]) {
printf("最大三角形的周长是%d\n组成最大三角形的三条边是%d,%d,%d", arr[i] + arr[i-1] + arr[i-2], arr[i-2], arr[i-1], arr[i]);
break;
}
}
}
return 0;
}
|
