杂题——「MYOI-R3」极差

T425609 「MYOI-R3」极差

原题

题目描述

对于一个序列 $c$ ，定义 $c$ 的极差为 $c$ 中最大值与最小值之差。现在给定一个长度为 $n$ 的序列 $a$，问是否能将其分成至少两个长度大于 $1$ 的子序列，使得每个子序列的极差都相等（注意，所有元素都必须分配且每个元素仅能分配到一个子序列中）。

输入格式

本题包含多组数据。

第一行两个整数 $T,id$，表示数据组数和子任务编号。

对于每组数据，

第一行一个正整数 $n$，表示数组长度。

第二行 $n$ 个整数表示序列 $a$。

输出格式

对于每组数据，输出一行一个字符串 Yes 或 No。

样例 #1

样例输入 #1

1
2
3
4
5
2 1
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0

样例输出 #1

1
2
No
Yes

提示

样例 $\small\text{1}$ 解释

样例符合子任务 1 的约束，$id=1$。

询问一：

可以证明，没有任何方案满足条件。

询问二：

合法分配的一种子序列集合如下：

  • ${1,9}$。
  • ${1,9}$。
  • ${8,1,0}$。

答案不唯一。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1（20 points）：$4\le \sum n\le 20,a_i\ge 0$。
  • Subtask 2（20 points）：$4\le \sum n\le 100,a_i\ge 0$。
  • Subtask 3（20 points）：$4\le \sum n\le 10^3,a_i\ge 0$。
  • Subtask 4（10 points）：$a$ 数组中元素相等。
  • Subtask 5（30 points）：无特殊限制。

对于 $100%$ 的数据，$4\le \sum n\le 10^6,0\le |a_i|\le 10^9,1\le T\le 300$。

思路

​ 这道题目说实话一开始还没想到这个思路,其实还是比较简单的,就这么一个思路:

​ 首先,我们对数组从小到大排序.注意排序之后这个数组第一个元素$a_1$和$a_n$是最大值,如果我们想找到至少两个序列的极差相同,那么是不是就一定存在这么两个数,$a_x, a_y$满足:$a_x-a_1==a_n-a_y$,如此即可分出至少两个序列了呀.然后稍微转换一下变为$a_x+a_y==a_1+a_n$.这样问题就转换为了,已知一个数,需要在剩下的数里面找到两个数的和等于这个数,来个二分$O(nlogn)$的时间复杂度,完全ok的也是.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 1e6 + 10;
int a[N];

void solve() {
	int n;
    cin >> n;
    fore (i, 1, n) cin >> a[i];
    
    sort (a + 1, a + n + 1);
    int kk = a[1] + a[n];
    bool flag = false;
    
    fore (i, 2, n - 1) {
        int x = kk - a[i];
        int l = i + 1, r = n - 1;
        bool fd=binary_search(a + i + 1,a + n, x);
        if (fd) {
            cout << "Yes" << ed;
            flag = true;
            break;
        }
    }
	
    if (!flag) cout << "No" << ed;
}


int main()
{
    
    int _ = 1, id;
    cin >> _ >> id;
    
    while(_--) {
        solve();
    }
    
    return 0;
}