# 题目大意
给你一个 A=(a1,...,an)，问你是否可以重排列成 B=(b1,...,bn) 使得 B 是一个等比数列
# 数据范围
- 1≤T≤105
- 2≤N≤2×105
- −109≤ai≤109
# 题解
A 可能有：
需要注意的是，正数负数交替的情况
- 必须满足，
max(正数个数, 负数个数) - min(正数个数, 负数个数) <= 1 - 注意，等比数列的公比 D 的绝对值，可能 ≥1 也可能 <1
- 如果
|D| >= 1 的话，那么序列绝对值应该是升序的 - 如果
|D| < 1 的话，那么序列绝对值应该是降序的
下面是我的屎山代码
C++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
| int n;
vector<int> a;
bool check(vector<int>& a) {
for (int i = 3; i <= n; i++)
if (a[i] * a[i - 2] != a[i - 1] * a[i - 1])
return false;
return true;
}
void solve () {
cin >> n, a = vector<int>(n + 1);
vector<int> num[2];
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > 0)
num[0].push_back(a[i]);
else if (a[i] < 0)
num[1].push_back(a[i]);
}
if (n <= 2) {
cout << "Yes\n";
return;
}
if (num[1].empty() || num[0].empty()) {
sort(a.begin() + 1, a.end());
cout << (check(a) ? "Yes" : "No") << '\n';
}
else {
bool flag1 = 0;
int idx = (num[0].size() >= num[1].size() ? 0 : 1);
if (num[idx].size() - num[1 - idx].size() > 1) {
cout << "No\n";
return;
}
sort(num[0].begin(), num[0].end());
sort(num[1].begin(), num[1].end(), [](int x, int y)
{ return x > y; });
a = vector<int>(1);
for (int i = 0; i < num[1 - idx].size(); i++)
a.push_back(num[idx][i]), a.push_back(num[1 - idx][i]);
if (num[idx].size() != num[1 - idx].size())
a.push_back(num[idx].back());
flag1 = check(a);
if (flag1) {
cout << "Yes\n";
return;
}
sort(num[1].begin(), num[1].end());
sort(num[0].begin(), num[0].end(), [](int x, int y)
{ return x > y; });
a = vector<int>(1);
for (int i = 0; i < num[1 - idx].size(); i++)
a.push_back(num[idx][i]), a.push_back(num[1 - idx][i]);
if (num[idx].size() != num[1 - idx].size())
a.push_back(num[idx].back());
cout << (check(a) ? "Yes" : "No") << '\n';
}
}
|
