首页 > 试题广场 >

相等序列

[编程题]相等序列

热度指数：5755 时间限制：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

算法知识视频讲解

孤天祭

JAVA的解题思路

满足条件的最容易想到的是用TreeSet存储，由于它的不重复和自然顺序特性，可能得到以下几种结果：

1.如果size<3，YES

2.如果size>3，No

3.如果size==3，只需比较末尾元素与中间元素的差值是否等于起始元素与中间元素的差值即可，如果相等为YES，否则为NO

附上代码

import java.util.TreeSet;
import java.util.Scanner;
public class Main{
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args){
        int k=Integer.parseInt(sc.nextLine());
        TreeSet<Integer> set=new TreeSet<Integer>();
        while(k--!=0){
            String str=null;
            int n=Integer.parseInt(sc.nextLine());
            String[] str0=sc.nextLine().split(" ");
            int j=0;
            while(n--!=0){
                set.add(Integer.parseInt(str0[j++]));
            }
            if(set.size()!=3){
                if(set.size()<3)
                    str="YES";
                else
                    str="NO";
            }else{
                int[] ar=new int[3];
                int i=0;
               for(int num:set){
                   ar[i++]=num;
               }
                if(2*ar[1]==ar[2]+ar[0]){
                    str="YES";
                }else{
                    str="NO";
                }
            }
            System.out.println(str);
            set.clear();
        }
    }
}

编辑于 2020-07-27 20:03:28 回复(0)

初心者托奇

for i in range(int(input())):
    input()
    b = sorted(set(map(int,input().split())))
    print('YES' if len(b) < 3 or sum(b) == 3 * b[1] else 'NO')

编辑于 2020-03-18 21:35:37 回复(0)

Disconnect

import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n;
        int[] arr;
        for(int i=0;i<k;i++)
        {
            n = sc.nextInt();
            arr = new int[n];
            for(int j=0;j<n;j++)
            {
                arr[j] = sc.nextInt();
            }
            if(arr.length<=2)
            {
                System.out.println("YES");
            }
            else{
                if(cando(arr))
                {
                    System.out.println("YES");
                }
                else{
                    System.out.println("NO");
                }
            }
        }
    }
    static boolean cando(int[] arr)
    {
        int max = max(arr);
        int min = min(arr);
        if((max-min)%2!=0)
        {
            return false;
        }
        int x = (max-min)/2;
        int flag = x+min;
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]!=min && arr[i]!=max && arr[i]!=flag)
            {
                return false;
            }
        }
        return true;
    }
    static int max(int[] arr)
    {
        int out = Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++)
        {
            out = Math.max(out,arr[i]);
        }
        return out;
    }
    static int min(int[] arr)
    {
        int out = Integer.MAX_VALUE;
        for(int i=0;i<arr.length;i++)
        {
            out = Math.min(out,arr[i]);
        }
        return out;
    }
}

发表于 2019-08-29 09:39:10 回复(1)

Robust-neu

//当序列中的数字种类大于3种，一定为NO，小于3种，一定为YES;
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{ 
    int k;
    cin >> k;
    while (k > 0) {
        int l;
        cin >> l;
        set<int> data;//用一个set记录数字种类
        while (l > 0) {
            int n;
            cin >> n;
            data.insert(n);
            l--;
        }
        vector<int> Num;
        Num.assign(data.begin(), data.end());
        if (Num.size() >= 4) cout << "NO" << endl;//>=4,为NO
        else if (Num.size() <= 2) cout << "YES" << endl;//<=2,为YES
        else {
            if (Num[2]-Num[1]==Num[1]-Num[0]) cout << "YES" << endl;//==3时进一步判断
            else cout << "NO" << endl;
        }
        k--;
    }
    return 0;
}

发表于 2019-07-30 15:42:28 回复(1)

pein531

数组中的元素去重后如果只有少于3个数，一定可以满足加减x操作后使得每个数组中的元素都相等；如果大于3个数一定做不到这一点；如果等于三个数，需要满足a<b<c且c-b=a-b。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        while(k-- > 0){
            int n = Integer.parseInt(br.readLine().trim());
            String[] strArr = br.readLine().trim().split(" ");
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
            if(judge(arr))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    
    private static boolean judge(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for(int num: arr) set.add(num);
        // 数组去重后肯定不能超过三个数
        if(set.size() > 3) return false;
        // 一个数和两个数是可以的
        if(set.size() == 1 || set.size() == 2) return true;
        // 三个数如果满足a<b<c且b-a=c-b，也是可以的
        int[] temp = new int[3];
        Iterator<Integer> iterator = set.iterator();
        int i = 0;
        while(iterator.hasNext()){
            temp[i] = iterator.next();
            i++;
        }
        Arrays.sort(temp);
        if(temp[2] - temp[1] == temp[1] - temp[0])
            return true;
        return false;
    }
}

发表于 2021-01-31 10:38:08 回复(0)

邂逅龙

#include<iostream>
#include<string>
#include<set>
using namespace std;
int main()
{
	int k;
	cin>>k;
	while(k--)
	{
		int n;
		int x;
		cin>>n;
		set<int> s;
		for(int i=0;i<n;i++)
		{
			cin>>x;
			s.insert(x);
		}
		set<int>::iterator it=s.begin();
		string ans;
		if(s.size()<3) ans="YES";
		else if(s.size()==3)
		{
			if((*s.begin()+*s.rbegin())==2*(*(++it))) ans="YES";
			else ans="NO";
		}
		else ans="NO";
		cout<<ans<<endl; 
	}
	return 0;
}

发表于 2020-08-17 18:08:36 回复(0)

Java

你的offer对我打了烊

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        for(int i = 0;i < k;i++){
            int n = Integer.parseInt(br.readLine());
            String[] str = br.readLine().split(" ");
            int[] arr = new int[n];
            for(int j = 0;j < n;j++){
                arr[j] = Integer.parseInt(str[j]);
            }
            System.out.println(eql(arr));
        }
    }
    public static String eql(int[] arr){
        Arrays.sort(arr);
        int a = arr[0];
        int b = arr[arr.length-1];
        if(arr.length == 2){
            return "YES";
        }
        if((a+b) % 2 != 0){
            return "NO";
        }
        int mid = (a+b)/2;
        int offset = b - mid;
        for(int i = 0;i < arr.length;i++){
            if(!(arr[i] + offset == mid || arr[i] - offset == mid || arr[i] == mid)){
                return "NO";
            }
        }
        return "YES";
    }
}

很黄很暴力

发表于 2020-04-19 21:33:01 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int n,t;
        cin>>n;
        set<int> hashset;
        for(int j=0;j<n;j++){
            cin>>t;
            hashset.insert(t);
        }
        set<int>::iterator it=hashset.begin();
        string ans;
        if(hashset.size()<3)
            ans="YES";
        else if(hashset.size()==3)
            ans= *(++it) * 2 ==*hashset.begin() + *hashset.rbegin() ? "YES":"NO";
        else
            ans="NO";
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2019-10-21 10:10:09 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int k,n;
    cin>>k;
    while(k--){
        cin>>n;
        int a[n];
        set<int> s;
        for(int i=0;i<n;i++){
            cin>>a[i];
            s.insert(a[i]);
        }
        if(s.size()<=2)
            cout<<"YES"<<endl;
        else if(s.size()==3){
            vector<int> v;
            for(set<int>::iterator it=s.begin();it!=s.end();it++)
                v.push_back(*it);
            if(v[2]-v[1]==v[1]-v[0])
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }else
            cout<<"NO"<<endl;
    }
    return 0;
}

发表于 2019-08-20 03:49:32 回复(0)

C/C++

广州市民林先生

思路分析：

序列的某些元素要同时增，减x之后能够保持所有元素值一样，直接整个遍历计算是不现实的。

我们知道，每次增，减的值应当是固定的，也就是x，那就说明比如：不能拿大的减1，小的加2这种形式，要么大的都减2，小的都加2；要么大的都减1，小的都加1。那要保证某两部分，一部分加x，一部分减x，最后要达到相等，那必然存在一个中介，这个中介是不能动的。就比如1 2 3这个序列，2是不能动的，1,3做减，加操作后，要和2相等，这就是我们所熟知的等差序列性质。那推广一下，1，2和3都可能都多个，比如1 1 1 2 2 2 3 3 3这种，但是唯一不变的就是数的类型只能有3种，不能说1 2 3 4这样子，那就不可能达到相等，因为上面分析过了，只能有1个中介。

思考到这里，就基本可以确定思路了：我们不需要拿出所有的数（1 1 1 2 2 2 3 3 3），而只需要取出一个样本（1 2 3），同时样本数不能超过3个（1 2 3 4是不可以的），然后拿这3个样本来进行等差数列的分析（a[0] + a[2] = 2*a[1]），满足的话ans = “YES”，否则ans = "NO"。当然，不要忘了样本可能只有1个或者2个，那必然ans = "YES"。

而要样本数只拿出一个，当然用的就是set容器了，利用它的去重和排序，我们可以省去大笔功夫，直接进行等差序列判断

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main(){
    int k;  //k个序列
    cin >> k;
    while(k--){
        int n;  //序列长度
        int num; //元素值
        cin >> n;
        set<int> res;  //存储每一行的元素，但是每种类型只能存1个，并且会排序
        for(int i = 0; i < n; ++i){
            cin>>num;
            res.insert(num);
        }
        set<int>::iterator it = res.begin();
        string ans;
        if(res.size() < 3){ 
            ans = "YES";
        }
        else if(res.size() == 3){
            //只能一增一减，又因为是有序的，所以第一个增，第三个减，第二个不变。
            //比如1 5 8 就是不可以的，1 5 9就是可以的，利用等差序列性质
            //注意这里不能用res.end,因为end是指向最后一个元素的下一个位置
            if((*res.begin() + *res.rbegin())/2 == *(++it)){
                ans = "YES";
            }
            else{
                ans = "NO";
            }
        }
        else{
            ans = "NO";
        }
        cout << ans << endl;
    }
    return 0;
}

编辑于 2020-03-27 13:17:09 回复(7)

Java

小谷围做题家

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        while(n>0){
            n--;
            int m=in.nextInt();
            Set<Integer> set=new HashSet();
            while(m>0){
                set.add(in.nextInt());
                m--;
            }
            if(set.size()>3){
                System.out.println("NO");
                continue;
            }else if(set.size()<=2){
                System.out.println("YES");
            }else{
                int[] arr=new int[3];
                int idx=0;
                for(int x:set){
                    arr[idx++]=x;
                }
                Arrays.sort(arr);
                if(arr[0]+arr[2]==arr[1]*2){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }
        }
    }
}

发表于 2023-09-06 21:41:17 回复(0)

C++

tridu33

0 0 50000 100000 50000 0 0 50000 0 100000

为什么这个测例要求“YES”？

发表于 2021-09-17 19:28:44 回复(0)

C/C++

牛客549207409号

#include<iostream>
#include<vector>
#include<set>
int main()
{
int k;
long n,a;
while(std::cin>>k)
{
for(int i=0;i<k;i++)
{
std::cin>>n;
std::set<long>s;
std::vector<long>t;
for(int j=0;j<n;j++)
{
std::cin>>a;
s.insert(a);
}
for(std::set<long>::iterator it=s.begin();it!=s.end();it++)
{
t.push_back(*it);
}
if(t.size()==1||t.size()==2)std::cout<<"YES"<<std::endl;
else if(t.size()==3&&t[1]-t[0]==t[2]-t[1])std::cout<<"YES"<<std::endl;
else std::cout<<"NO"<<std::endl;
}
}
return 0;
}

发表于 2020-09-13 12:03:00 回复(0)

求上岸岸岸岸！！！

它这个n一点用都没有，这不是误导我们吗。。。。。

k = int(input())
for _ in range(k):
#data = list(map(int, input().split()))
input()
data = sorted(set(map(int,input().split())))
#data.sort()
if len(data) == 3 and (data[2]+data[0]) == 2*data[1] or len(data) < 3:
print("YES")
else:
print("NO")

发表于 2020-08-03 15:38:45 回复(0)

hesen

我提交的10几次(大部分是找错)，关于这道题我就说两个特别坑的地方，第一 x不一定为整数，可以为小数。第二不要提前break，因为这次未读入的数据会被当成下一次的输入(从leetcode过来，还真不适应从控制台输入输出)。最后我吐槽一下，测试用例显示成那个样子，根本起不到参考意义好吗！！！

发表于 2020-07-31 19:08:56 回复(0)

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)

柠檬小精灵

k = int(input())  #k个序列

a = []
b = []
for i in range(2*k):
    if i % 2 == 0:       #偶数行
        a.append(int(input()))  #代表给定长度
    else:
        b.append(input().split())

for i in range(k):
    c = []
    for j in range(a[i]):
        c.append(int(b[i][j]))
    if len(c) <= 2:
        print("YES")
    else:
        num = c.count(max(c)) + c.count(min(c)) + c.count((max(c) + min(c))/ 2)
        if num == len(c):
            print("YES")
        else:
            print("NO")

发表于 2020-06-18 11:00:56 回复(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)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main(){
    // 按照题意 这个数字序列最多只能有3种不同的数字 不然没办法凑成
    // 当包含3个不同值要能构成等差数列
    int k;
    cin>>k;
    unordered_map<int,int>mp;
    while(k--){
        mp.clear();
        int n;
        cin>>n;
        int x;
        while(n--){
            cin>>x;
            mp[x]=1;
        }
        int flag = 1;
        if(mp.size()>3) flag=0;
        else if(mp.size()==3){
            vector<int>tmp;
            for(auto t:mp)
                tmp.push_back(t.first);
            sort(tmp.begin(),tmp.end());
            if(tmp[2]-tmp[1]!=tmp[1]-tmp[0])
                flag = 0;
        }
        cout<<(flag?"YES":"NO")<<endl;
    }
    return 0;
}

发表于 2020-06-06 16:04:31 回复(0)

牛客652172042号

k = int(input())
for i in range(k):
    n = int(input())
    s = list(map(int, input().split()))
    a = set(s)
    s = list(a)
    s = sorted(s)
    if len(s) == 1&nbs***bsp;len(s) == 2:
        print('YES')
    if len(s) > 3:
        print('NO')
    if len(s) == 3:
        if s[2] - s[1] == s[1] - s[0]:
            print('YES')
        else:
            print('NO')

发表于 2020-05-02 18:56:21 回复(0)