首页 > 试题广场 >

数字圆环

[编程题]数字圆环
  • 热度指数：2268 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易有一个长度为n的数字数组a_1, a_2, …, a_n。

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

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

。


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

输入

1
5
17 6 17 11 17

输出

YES
示例2

输入

1
3
1 2 4

输出

NO
算法知识视频讲解
添加回答
暮成头像 暮成 
#include <iostream>
using namespace std;
int main()
{
    int t ;
    cin >> t;
    while(t>0)
    {
    long long  n ;
    cin >> n;
        if(n<=2)
            cout << "NO" << endl;
        else
        {
        long long a[n];
        for(long long i =0;i<n;i++)
        cin >> a[i];
        
        //直接找最大值 次最大值 次次最大值
        long long max = a[0];
        long long ccmax = 0;
        long long cmax = 0;
        for(long long i=1;i<n;i++)
        {
            if(a[i]>=max)
            {
                ccmax = cmax;
                cmax = max;
                max = a[i];
            }
            else if (a[i] >= cmax)
               {
                ccmax = cmax;
                cmax = a[i];             
            }              
            else if (a[i] >= ccmax)    
            {                 
                ccmax = a[i];             
            }

        }
  
        if(ccmax+cmax>max)    //最大值小于后两个之和  则所有都满足条件
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        }
     t--;
    }
}
编辑于 2020-08-19 08:52:42 回复(0)
祈求offer头像 祈求offer 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        while (t-- != 0) {
            int n = cin.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = cin.nextLong();
            }
            Arrays.sort(a);
            if (a[n-2] + a[n-3] > a[n-1]){ //只要只要最后二个和第一个加起来大于最后一个
                                                        //可以考虑将最后一个往前交换一位，这样都能满足条件
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}



编辑于 2020-08-07 11:29:39 回复(2)
pein531头像 pein531
由于a1 + a3 > a2，假设此时a2>a3且a2>a1，则a4选择最小的数字可以满足环的条件（a4最小，所以满足a3 + a1 > a4，而此时由于a2>a3成立，所以a2 + a4 > a3也成立）。现在考虑a5的情况，根据之前的分析，我们希望放一个比a4还小的数，但是a4已经是最小的数了，所以退而求其次，a4放倒数第二小的数，最小的数为a5，如此递归下去可以得到a4>a5>...>an。
完成所有递归的时候显然a4已经很大了，为第4大的数，a2为最大的数，此时取a1为第2大的数，a3为第3大的数即可。此时就相当于对数组降序排列后交换第一大和第二大的数，而由于对称性，所以升序排列后再交换也仍然等价。 
t = int(input())
while t:
    n = int(input())
    arr = list(map(int, input().strip().split()))
    arr.sort()
    arr[-1], arr[-2] = arr[-2], arr[-1]
    for i in range(n):
        pre, pos = (i - 1 + n) % n, (i + 1) % n   # 前一个数和后一个数的索引
        if arr[i] >= arr[pre] + arr[pos]:         # 相邻数的和大于等于中间的数，不符合要求
            print("NO")
            break
    else:
        # 循环正常执行完了才会走else，如果中途退出了不会执行
        print("YES")
    t -= 1


发表于 2020-10-22 10:46:38 回复(0)
黑暗过后会是晨曦头像 黑暗过后会是晨曦

因为每个数字小于相邻只和，直接排序数组，然后只要操作最大数左右两边之和大于最大数，此时只需要将最大数和第二大数交换位置即可。

发表于 2020-02-26 10:22:10 回复(4)
Python
七耀之心头像 七耀之心
最大的数大于等于（第二大的数+第三大的数）就不能组成环。所以 
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    a.reverse()
    if a[0] >= a[1] + a[2]:
        print('NO')
    else:
        print('YES')


发表于 2020-10-22 17:01:28 回复(0)
Java
xuanlGo头像 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)
universal猿头像 universal猿
思路：使用我们在所有情况中只要找到一种包含这样的情况即可，首先考虑最大的值是否能够介于两个数之间，如果不可以，则不用考虑其他情况；最有可能大于最大数的两个值是第二数 和第三大数，其他的数按照最小到大排序即可，因为左边的数总是比右边的大也肯定大于相邻两个数之和。
Implemention：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool judge(vector<long long > vec)
{
   long long  ccmax,cmax,max;

    sort(vec.begin(),vec.begin()+3);
    max= vec[2];
    cmax = vec[1];
    ccmax = vec[0];
    
    for(int  i  =3;i < vec.size();i++)
    {
        if(vec[i]> max )
        {
            ccmax = cmax;
            cmax = max;
            max = vec[i];
        }
        else if(vec[i] > cmax)
        {
            ccmax = cmax;
            cmax = vec[i];
        }
        else if(vec[i] > ccmax)
        {
            ccmax = vec[i];
        }
    }

    if(max < ccmax+cmax)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
   int  T;
   cin>>T;
   vector<vector<long long> > input;
  
   for(int i = 0;i < T;i++)
   {
       int  n;
       cin>> n;
       vector<long long> temp;
       for(long long  j  = 0;j < n;j++)
       {
           long long  elem;
           cin>>elem;
           temp.push_back(elem);
       }
       input.push_back(temp);
    }
   for(int i = 0;i < T;i++)
   {
         if(input[i].size() < 3)
        {
            cout<<"NO"<<endl;
           // return 0;
             continue;
        }    

       if(judge(input[i])){
           cout<<"YES"<<endl;
       }
       else{
           cout<<"NO"<<endl;
       }
   }

}

测试结果：
您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例
发表于 2020-08-23 19:23:19 回复(0)
Python
ΔtZ.头像 ΔtZ.
数组排序，最大值和次大值交换位置，中间值小于两边之和即满足条件 
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a[-1], a[-2] = a[-2], a[-1]
    for i in range(n):
        pre, pos = (i - 1)%n, (i + 1) % n
        if a[i] >= a[pre] + a[pos]:
            print("NO")
            break
    else:
        print("YES")


发表于 2020-08-15 15:45:01 回复(0)
理想汽车部门直推官头像 理想汽车部门直推官
通过比较大小最优排列 
t = int(input())
while t:
    n = int(input())
    data = list(map(int, input().split()))
    data.sort()
    data[-1], data[-2] = data[-2], data[-1]
    for i in range(n):
        pre, pos = (i - 1 + n)%n, (i + 1) % n
        if data[i] >= data[pre] + data[pos]:
            print("NO")
            break
    else:
        print("YES")
    t -= 1


编辑于 2020-08-08 09:49:04 回复(0)
fight2020头像 fight2020 
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = float('-inf'), float('-inf'), float('-inf')
    for num in a:
        if num>c1:
            c3 = c2
            c2 = c1
            c1 = num
        elif num>c2:
            c3 = c2
            c2 = num
        elif num>c3:
            c3 = num
            
    if c3+c2<c1:
        print('NO')
    else:
        print('YES')

一开始想最小两个的和 大于最大一个 想差了 这个情况感觉 就是完全能过 
两个倒数最大的和 大于最大 是临街情况 就像示例那样
发表于 2020-08-08 07:51:59 回复(0)
阿杰不是本地人头像 阿杰不是本地人
通过---AC
先把数组由小到大排序，然后只要确定最大的数在第二大数与第三大的数的和之间，就尅满足条件。
def cir_number(test_num):
    for x in range(test_num):
        n = int(raw_input())
        nums = sorted(list(map(int, raw_input().split())))
        if nums[-1]<nums[-3]+nums[-2]:
            print 'YES'
        else:
            print 'NO'
test_num=int(raw_input())
cir_number(test_num)

发表于 2020-08-07 17:34:50 回复(0)
牛客717970517号头像 牛客717970517号 
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t>0)
	{
		int n;
		cin >> n;
		long long* a;
		a = new long long[n];
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		sort(a, a + n);
		long long max = a[n - 1];
		long long cmax = a[n - 2];
		long long ccmax = a[n - 3];

		if (ccmax + cmax > max)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		delete[]a;
		a = NULL;
		t--;
	}
}
本地编译器VS不支持变长数组int a[n]，用new在堆区，可以
发表于 2020-08-07 13:35:39 回复(0)
成都无线华为招聘头像 成都无线华为招聘 
import java.util.Scanner;
public class Main{
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0;i < T;i++){
            int n = sc.nextInt();
            long[] arr = new long[n];
            boolean flag = true;
            for(int j = 0;j < n;j++){
                arr[j] = sc.nextLong();
            }
            if(arr[0] != arr[arr.length - 1]){
                System.out.println("NO");
                continue;
            }

            for(int k = 1;k < arr.length - 1;k++){
                if((arr[k - 1] + arr[k + 1]) < arr[k]){
                    flag = false;
                }
            }
            if(flag){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}
case 30%
发表于 2020-08-07 10:36:17 回复(0)
Rho_A1As头像 Rho_A1As 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t > 0){
            t--;
            long length = sc.nextInt();
            LinkedList<Long> nums = new LinkedList<>();
            while(length > 0){
                nums.add(sc.nextLong());
                length--;
            }
            String s = method(nums)? "YES":"NO";
            System.out.println(s);
        }
    }
    public static boolean method(LinkedList<Long> nums){
        if(nums == null || nums.size() <= 2){
            return false;
        }
        Collections.sort(nums);
        long a1 = nums.removeLast();
        long a2 = nums.removeLast();
        long a3 = nums.removeLast();
        return a1 < a2 + a3;
    }
}

发表于 2020-08-04 16:58:59 回复(0)
7845头像 7845 
import java.util.Scanner;
public class Main{
    public static  void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int t=sc.nextInt();
        int n= sc.nextInt();
        long[][] martix=new long[t][ n];
        for(int i=0;i<t;i++){
            for(int j=0;j<n;j++){
                martix[i][j]=sc.nextLong();//读取要用long，长整型
            }
        }
        long[] count= new long[t];
        for(int i=0;i<t;i++) {//判断第一个数和最后一个数
            if (martix[i][0] > martix[i][1] + martix[i][n - 1]) {
                count[i]++;
            }
            if(martix[i][n - 1] > martix[i][n - 2] + martix[i][0]){
                count[i]++;
            }
            for (int j = 1; j < n - 1; j++) {
                if (martix[i][j] > martix[i][j - 1] + martix[i][j + 1]) {
                    count[i]++;
                }
            }
        }
        for (int i=0;i<t;i++){
            if (count[i]==0){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}
case20%,提示数组越界等非法访问情况

发表于 2020-08-04 15:39:52 回复(0)
牛客322242703头像 牛客322242703 
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int i = 0;i < t;i++){

            int n = Integer.parseInt(br.readLine());
            String[] str = br.readLine().split(" ");
            long[] arr = new long[n];
            for(int j = 0;j < n;j++){
                arr[j] = Long.parseLong(str[j]);
            }
            if(isCircle(arr,n))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    public static boolean isCircle(long[] arr,int n){
        Arrays.sort(arr);
        if(arr[0] + arr[n-2] > arr[n-1])
            return true;
        else if((arr[0] + arr[n-1] > arr[n-2]) && (arr[n-2] + arr[n-3] > arr[n-1]))
            return true;
        return false;
    }
}
数组要用long
编辑于 2020-07-26 09:38:16 回复(3)
Python
zai等一个offer头像 zai等一个offer
通过了，一开始理解错了三个输入，总是20% 
def y_n(t):

    for j in range(t):
        n = int(input())
        x = list(map(int, input().split(' ')))
        Y_N = 'YES'
        #x = X[j]
        y = x[0:1]
        for i in range(2,n):
            if x[i] < (x[i-1]+x[i-2]):   # 小于两数和插入中间，大于等于则加在后面
                y.insert(i-1, x[i])
            else:
                y.append(x[i])
        if (y[0]+y[-2]) < y[-1]:
            Y_N='NO'
        print(Y_N)

t = int(input())
#n = int(input())
#X = list(map(int, input().split(' ')))
# a=int(n/m)
# X=[X[i:i+a] for i in range(0, n, a)]   # 将数据分成m组，存入listX
#X=[X[i:i+n] for i in range(0, len(X), n)]   # 将数据分成m组，存入listX
# print(X)
y_n(t)


编辑于 2020-07-21 12:46:49 回复(0)
lyj_999头像 lyj_999
这一题不用考虑负数吗？
发表于 2020-07-15 09:23:09 回复(1)
🍅一只番茄仔头像 🍅一只番茄仔 
def circle(num):
    l=len(num)
    sorted(num)
    if num[l] < num[0] + num[l-1]:
        a= num[l]
        num[l]=num[l-1]
        num[l-1]=a
        return num
    else:
        return num


nums=list(map(int, input().split()))
res = circle(nums)
print(res)

发表于 2020-06-03 19:49:28 回复(0)
旧时明月曾照我头像 旧时明月曾照我

case20%,提示数组越界等非法访问情况

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        while(n>0){
            int m=in.nextInt();
            int [] a=new int[m];
            for(int i=0;i<m;i++){
                a[i]=in.nextInt();
            }
            CountingSort(a);
            int k=a[m-1];
            a[m-1]=a[m-2];
            a[m-2]=k;
            int flag=1;
            for(int i=0;i<m-2;i++){
                if(a[i]+a[i+2]<a[i+1]){
                    flag=0;
                }
            }
            if(flag==1){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
            n--;
        }
    }
    public static int[] CountingSort(int[] array) {
        if (array.length == 0) {
            return array;
        }         
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }             
            if (array[i] < min){
                min = array[i];
            }
        }
        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else{
                i++;
            }             
        }
        return array;
    }
}
编辑于 2020-02-27 10:22:47 回复(6)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 网易 算法工程师 测试开发工程师 安全工程师 2020 数据库工程师 Java工程师
上传者：小小
难度：
20条回答 6134浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号