Ntarsis' Set

发表于 分类于 ，

    给出$1, 2, 3, \ldots, 10^{1000}$的序列，此外给出一个数组$a_1, a_2, \ldots, a_n$，对于所有$1\le i \le n$每次同时删除序列中第$a_i$个元素。

    问删除k次后，最小的元素是多少。

Ntarsis’ Set

Created by LXC on Wed Oct 18 01:32:45 2023

https://codeforces.com/problemset/problem/1852/A

ranting: 1800

tag: binary search, math, number theory

problem

给出$1, 2, 3, \ldots, 10^{1000}$的序列，此外给出一个数组$a_1, a_2, \ldots, a_n$，对于所有$1\le i \le n$每次同时删除序列中第$a_i$个元素。

问删除k次后，最小的元素是多少。

solution

逆向考虑问题

如果最后一次删除后最小元素为$x_0$。

最后一次删除前，$x_0$所在位置应该是$a_1, a_2, \ldots, a_n$中第一个未出现的正整数，设其为$x_1$。

倒数第二次删除前，$x_1$所在位置应该是$a_1, a_2, \ldots, a_n$中第$x_0$个未出现的正整数，设其为$x_2$。

…

第一次删除前，$x_{k-1}$所在位置应该是$a_1, a_2, \ldots, a_n$中第$x_{k-2}$个未出现的正整数，设其为$x_k$。

$x_k$就是我们要的答案。

code

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

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll& i:a) cin >> i;
    vector<pair<ll,ll>> p; 
    if (a[0] != 1) p.emplace_back(a[0]-1, 1);
    for (int i=1; i<n; i++) {
        if (a[i] != 1+a[i-1]) p.emplace_back(a[i]-a[i-1]-1, a[i-1]+1);
    }
    p.emplace_back(1e15, a[n-1]+1);
    // for (auto [i,j]:p) {
    //     cout << i << " " << j << endl;
    // }
    ll j = 0, c = 1, stp = 0;
    for (int i=0; i<k; i++) {
        while (p[j].first+stp < c) {
            stp += p[j].first;
            j++;
        }
        c = p[j].second + c-stp - 1;
        // if (c > a[n-1]) break;
    }
    cout << c << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}