• 【每日一题】补档 ARC134D - Concatenate Subsequences | 思维 | 简单


    题目内容

    原题链接

    给定一个长度为 2 n 2n 2n 的数组,问使得这个数组的字典序最小,最后的数组是什么样。

    每次操作可以选择一个 index ,删除 a [ i n d e x ] a[index] a[index] a [ i n d e x + n ] a[index+n] a[index+n] ,但是数组最后不能为空

    数据范围

    • 1 ≤ n ≤ 1 0 5 1\leq n\leq 10^5 1n105
    • 1 ≤ a i ≤ 1 0 9 1\leq a_i\leq 10^9 1ai109

    题解

    因为最终剩余的部分以原本的前 n n n 个数的大小为准,所以这里以前 n n n 个数作一个单调非递减的序列 v e c vec vec v e c vec vec 是存储每个数的索引

    这里令后 n n n 个为 b b b ,即 b [ i ] = a [ i + n ] b[i]=a[i+n] b[i]=a[i+n]

    如果 b [ v e c [ 0 ] ] ≤ a [ v e c [ 0 ] ] b[vec[0]]\leq a[vec[0]] b[vec[0]]a[vec[0]] ,那么这是最短的,即为答案。

    否则 b [ v e c [ 0 ] ] > a [ v e c [ 0 ] ] b[vec[0]]>a[vec[0]] b[vec[0]]>a[vec[0]] ,那么我们需要分类讨论:
    此时已经选了 i i i v e c vec vec 中的元素,那么必然是前 i i i 个,接下来继续考虑第 i + 1 i+1 i+1 个即 v e c [ i ] vec[i] vec[i]

    • a [ v e c [ i ] ] > b [ v e c [ 0 ] ] a[vec[i]] > b[vec[0]] a[vec[i]]>b[vec[0]] ,没必要选择后面的了。
    • a [ v e c [ i ] ] < b [ v e c [ 0 ] ] a[vec[i]] < b[vec[0]] a[vec[i]]<b[vec[0]] ,那么 v e c [ i ] vec[i] vec[i] 相同的都选上。
    • a [ v e c [ i ] ] = b [ v e c [ 0 ] ] a[vec[i]] = b[vec[0]] a[vec[i]]=b[vec[0]] ,那么需要考虑已经选择的部分,如果 b [ v e c [ 0 ] ] b[vec[0]] b[vec[0]] b [ v e c [ i − 1 ] ] b[vec[i-1]] b[vec[i1]] ,存在一个 j j j 满足 b [ v e c [ j ] ] > b [ v e c [ j − 1 ] ] b[vec[j]]>b[vec[j-1]] b[vec[j]]>b[vec[j1]] b [ v e c [ k ] ] = b [ v e c [ k − 1 ] ] , 0 ≤ k < j b[vec[k]]=b[vec[k-1]], 0\leq kb[vec[k]]=b[vec[k1]],0k<j ,那么我们就添加上这部分,使得这个字典序上升的更慢。

    时间复杂度: O ( n ) O(n) O(n)

    代码

    #include 
    using namespace std;
    
    void solve() {
        int n;
        cin >> n;
    
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];
    
        vector<int> vec;
        for (int i = 0; i < n; ++i) {
            while (!vec.empty() && a[i] < a[vec.back()]) vec.pop_back();
            vec.push_back(i);
        }
    
        // vec 是一个递增的
        int len = int(vec.size());
        int cur = 0;
        int minv = b[vec[0]];
        int state = 0;
        for (int i = 0; i < len && a[vec[i]] == a[vec[0]]; ++i) {
            minv = min(minv, b[vec[i]]);
            cur = i;
            if (i > 0) {
                if (state == 0) {
                    if (b[vec[i]] > b[vec[i - 1]]) state = 1;
                    else if (b[vec[i]] < b[vec[i - 1]]) state = -1;
                }
            }
        }
    
        if (minv <= a[vec[0]]) {
            cout << a[vec[0]] << " " << minv;
            return;
        }
    
        for (int i = cur + 1; i < len; ++i) {
            if (a[vec[i]] < b[vec[0]] || (a[vec[i]] == b[vec[0]] && state == 1)) {
                int j = i;
                while (j < len && a[vec[j]] == a[vec[i]]) {
                    if (state == 0) {
                        if (b[vec[j]] > b[vec[j - 1]]) state = 1;
                        else if (b[vec[j]] < b[vec[j - 1]]) state = -1;
                    }
                    j += 1;
                }
                cur = j - 1;
                i = j - 1;
            } else {
                break;
            }
        }
    
        for (int i = 0; i <= cur; ++i) cout << a[vec[i]] << " ";
        for (int i = 0; i <= cur; ++i) cout << b[vec[i]] << " \n"[i == cur];
    
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int T = 1;
    //    cin >> T;
        while (T--) {
            solve();
        }
    
        return 0;
    }
    
    • 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
  • 相关阅读:
    【Spring中的设计模式】
    taichi库记录
    设计模式之迭代器模式
    迷你无人车 Gazebo 仿真
    【MySQL知识点】默认约束、非空约束
    【解刊】IEEE(Trans)系列,CCF-A类顶刊,国人友好,无需版面费!
    Sqlserver 多行合并为一行
    Excel 转 Json 、Node.js实现(应用场景:i18n国际化)
    调研主板,树莓派 VS RK3288板子,还是 RK的主板香,但是只支持 anrdoid 7系统,估计也有刷机成 armbian或者
    springboot服务端接口公网远程调试 - 实现HTTP服务监听【端口映射】
  • 原文地址:https://blog.csdn.net/weixin_43900869/article/details/134081091