思路:反向推x可以由哪些等级的种子得到。
AC代码:
#include<vector>
#include<cstring>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
#define fi first
#define se second
const int Max = 1e5 + 5;
PLL tree[20];
int a[Max];
int main() {
int n;
ll x;
cin >> n;
int max_a = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > max_a)
max_a = a[i];
}
cin >> x;
tree[0].fi = x;
tree[0].se = x;
int layers = 1;
while (tree[layers - 1].se < max_a) {
tree[layers].se = tree[layers - 1].se * 3;
tree[layers].fi = tree[layers - 1].fi * 3 - 2;
layers++;
}
ll result[20];
for (int i = 0; i < 20; i++)
result[i] = 0;
for (int i = 1; i <= n; i++) {
int j = 0;
while (a[i] > tree[j].se) {
j++;
}
if (j == 0 && a[i] == x) {
result[j]++;
}
else if (j > 0) {
if (tree[j].fi <= a[i]) {
result[j] += (1 << j);
}
}
}
ll ans = 0;
for (int i = 0; i < layers; i++) {
if (result[i] > ans)
ans = result[i];
}
cout << ans;
return 0;
}