首页 > 试题广场 >

数字圆环

[编程题]数字圆环

热度指数：2268 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小易有一个长度为n的数字数组 $a_1$ , $a_2$ , …, $a_n$ 。

问你是否能用这n个数字构成一个环(首尾连接)，使得环中的每一个数字都小于它相邻的两个数字的和(每个数字都必须使用并且每个数字只能使用一次)。

输入描述:

第一行包含一个整数t(1<=t<=10)，表示测试用例的组数。
每个测试用例输入如下：
第一行一个整数n，表示数字的个数；
第二行n个整数, , …, ，每两个整数之间用一个空格分隔。
输入数据保证

。

输出描述:

输出应该包含t行，对于每组用例，若能输出"YES"，否则输出"NO"。

示例1

输入

1
5
17 6 17 11 17

输出

YES

示例2

输入

1
3
1 2 4

输出

NO

算法知识视频讲解

Java

xuanlGo

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while ( t-- != 0){
            int n = sc.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextLong();
            }
            System.out.println(solution(a));
        }

    }


    public static String solution(long arr[]){
        Arrays.sort(arr);
        if (arr[arr.length-1] < arr[0] + arr[arr.length-2])
        {
            return "YES";
        }else {
            swap(arr,arr.length-1,arr.length-2);
            if (arr[arr.length - 2] < arr[arr.length - 3] + arr[arr.length-1]){
                return "YES";
            }else {
                return "NO";
            }

        }


    }

    private static void swap(long[] arr, int i, int i1) {
        arr[i] = arr[i1] ^ arr[i];
        arr[i1] = arr[i] ^ arr[i1];
        arr[i] = arr[i] ^ arr[i1];
    }
}

发表于 2020-08-31 17:19:22 回复(0)