解题思路

这是一道序列判定题目，主要思路如下：

  1. 关键观察：

    • 每个元素最多只能被操作一次（加 或减 ）
    • 要使所有元素相等，最终值必须是原序列中的某个值

  2. 判断条件：

    • 如果去重后元素个数小于3，一定可以实现
    • 如果去重后元素个数大于3，一定不能实现
    • 如果去重后正好3个元素，中间值必须是两端值的平均值

  3. 优化：

    • 使用 set 自动去重并排序
    • 使用迭代器访问首、中、尾元素

代码

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

int main() {
    int k;
    cin >> k;
    
    while(k--) {
        int n;
        cin >> n;
        
        // 使用set去重
        set<int> nums;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            nums.insert(x);
        }
        
        // 判断是否可能实现
        if(nums.size() < 3) {
            cout << "YES" << endl;
        }
        else if(nums.size() > 3) {
            cout << "NO" << endl;
        }
        else {
            // 检查三个数是否满足条件
            auto it = nums.begin();
            int first = *it;
            int second = *(++it);
            int third = *(++it);
            
            if(second * 2 == first + third) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        while(k-- > 0) {
            int n = sc.nextInt();
            
            // 使用TreeSet去重并排序
            TreeSet<Integer> nums = new TreeSet<>();
            for(int i = 0; i < n; i++) {
                nums.add(sc.nextInt());
            }
            
            // 判断是否可能实现
            if(nums.size() < 3) {
                System.out.println("YES");
            }
            else if(nums.size() > 3) {
                System.out.println("NO");
            }
            else {
                // 检查三个数是否满足条件
                Iterator<Integer> it = nums.iterator();
                int first = it.next();
                int second = it.next();
                int third = it.next();
                
                if(second * 2 == first + third) {
                    System.out.println("YES");
                }
                else {
                    System.out.println("NO");
                }
            }
        }
    }
}

def can_make_equal(n, nums):
    # 去重
    unique_nums = sorted(set(nums))
    
    # 判断是否可能实现
    if len(unique_nums) < 3:
        return "YES"
    elif len(unique_nums) > 3:
        return "NO"
    else:
        # 检查三个数是否满足条件
        if unique_nums[1] * 2 == unique_nums[0] + unique_nums[2]:
            return "YES"
        return "NO"

def main():
    k = int(input())
    
    for _ in range(k):
        n = int(input())
        nums = list(map(int, input().split()))
        print(can_make_equal(n, nums))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：集合去重 + 数学判定
  • 时间复杂度： - 为测试用例数， 为序列长度
  • 空间复杂度： - 需要存储去重后的序列