相等序列

[编程题]相等序列

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

题目给定a₁,a₂...a_n，这样一个长度为n的序列，现在你可以给其中一些元素加上一个值x（只能加一次），然后可以给另外一些值减上一个值x（只能减一次），剩下的元素不能再进行操作。问最后有没有可能找到一个值x使所有元素的值相等。

输入描述:

输入第一行为一个整数k，代表有k个序列(k<100)，接下来有2*k行:
偶数行为一个整数n，代表给定序列的长度(1<=n<=100,000)
奇数行包含n个元素，a₁,a₂...a_n，代表序列中的元素(0<=a_i<=100,000)

输出描述:

输出k行，每行一个YES或者NO

示例1

输入

1
5
1 3 3 2 1

输出

YES

算法知识视频讲解

Python

我不想当大白菜

根据题目的要求，对每个值只能进行一次加、减或不更改的操作，所以如果数组中unique的值大于等于4时一定不满足条件，小于等于2时一定满足条件，等于三时再比较三个书中是否存在一个数，使得另外两个数减去它的绝对值相等。

def check_valid(N,nums):
    unique_values = set(nums)
    if len(unique_values) < 3:return "YES"
    elif len(unique_values) >= 4:return "NO"
    for val1 in unique_values:
        abs_minus_vals = set()
        for val2 in unique_values - set([val1]):
            abs_minus_vals.add(abs(val1-val2))
            if len(abs_minus_vals) > 1:
                break
        if len(abs_minus_vals) == 1:
            return "YES"
    return "NO"

T = int(input())
for t in range(T):
    N = int(input())
    nums = list(map(int,input().split()))
    print(check_valid(N,nums))

发表于 2020-07-16 12:53:15 回复(0)

Python

鹿几

看评论感觉自己的方法过于暴力了emmmm

def solution(nums, x, mid):
    for k in nums:
        if k > mid:
            if k - x != mid:
                return False
        elif k < mid:
            if k + x != mid:
                return False
    return True


import sys

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    k = int(lines.pop(0).strip())
    for _ in range(k):
        n = int(lines.pop(0).strip())
        A = list(map(int, lines.pop(0).strip().split()))
        from collections import Counter

        B = sorted(Counter(A))
        *** = abs(B[-1] - B[0])
        if *** % 2 == 0:
            res = solution(A, ***, B[-1]) or solution(A, ***, B[0]) or solution(A, *** // 2,
                                                                                      (B[-1] + B[0]) // 2)
        else:
            res = solution(A, ***, B[-1]) or solution(A, ***, B[0])
        if res:
            print('YES')
        else:
            print("NO")

编辑于 2020-06-06 23:53:17 回复(0)