转换公式
加的数 0 1 2 3 4
原数组 2 4 6 2 5
满足条件 2 5 8 5 9
加之后 2 6 10 8 13
就是从n开始,能不能找到一条路可以到达的最大值,我们可以按满足条件的数组来从小到大排序,从n开始拼接,遇到可以拼接的就打上标记,打擂台找最大值
const int N = 3e5 + 10;
struct node
{
int os, x, y;
}a[N];
int cmp(node l, node r)
{
if (l.x == r.x) return l.y < r.y;
return l.x < r.x;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].os;
a[i].x = a[i].os + (i - 1);
a[i].y = a[i].os + 2 * (i - 1);
}
sort(a + 1, a + 1 + n, cmp);
map<int, int> p;
p[n] = 1;
int mmax = n;
for (int i = 1; i <= n; i++)
{
if (p[a[i].x] == 1)
{
mmax = max(mmax, a[i].y);
p[a[i].y] = 1;
}
}
cout << mmax << '\n';
}