1430E - String Reversal (树状数组、队列)

淩亂°似流年 2021-07-16 16:31 261阅读 0赞

[题目][Link 1]

思路：首先贪心一下，我们想要使得移动次数最小那肯定用前面离得近的元素去移动，所以我们用一个que来记录各个元素的位置，每使用完这个前面的位置的就pop掉。其次对于每一次移动我们需要知道它之前还剩多少个元素在这我们用树状数组来维护，每移去一个元素我们就让这个元素-1，初始时都为0.然后每次操作只需+que(i)-1的贡献即可。

如：3 4 5 3 7 6 3

假设我把7移到了最前面（干脆直接当作7不存在了） 3 4 5 3 (7) 6 3，那么对于原本7后面的6 3，他们下一步想要移到队首需要交换的次数比原来的次数少了一次，而对于原本7前面的数3 4 5 3它们想移动到队首所需的次数不变，而树状数组在这的运用就是改变单个点的值，直接查询区间的和（原本每个位置初始值为1表示距离，去掉之后值为0），契合树状数组。

#include<iostream>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    #define lowbit(x) (x&(-x))
    int c[Max], n;
    
    void add(int x, int v){ for (int i = x;i <= n;i += lowbit(i))c[i] += v;}
    int que(int x)
    { 
        int ans = 0;
        for (int i = x;i != 0;i -= lowbit(i))ans += c[i];
        return ans;
    }
    
    queue<int> q[27];
    char lst[Max];
    int main()
    { 
        cin >> n;
        for (int i = 1;i <= n;i++)
        { 
            char a;cin >> a;lst[i] = a;
            q[a - 'a'].push(i);
            add(i, 1);
        }
        ll ans = 0;
        for (int i = n;i >= 1;i--)
        { 
            int pre = q[lst[i] - 'a'].front();
            q[lst[i] - 'a'].pop();
            ans+=que(pre) - 1;
            add(pre, -1);
        }
        cout << ans << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1430/E

发表评论取消回复

表情：

评论列表（有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读

相关树状数组

详细介绍：[https://www.cnblogs.com/xenny/p/9739600.html][https_www.cnblogs.com_xenny_p_973960

我不是女神ヾ/ 2023年08月17日 16:26/ 0 赞/ 122 阅读

相关树状数组

目录： 1. 概念 2. 应用 3. 充分性 4. 建立树状数组 5. 典题分析一.概念数组来模拟树形结构。那么、为什么不直接建树？没必要，因为树

秒速五厘米/ 2023年02月25日 11:29/ 0 赞/ 25 阅读

相关树状数组

1、概述树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题：数组\{a

朱雀/ 2022年08月10日 10:53/ 0 赞/ 256 阅读

相关树状数组

树状数组树状数组：用线性数据结构的方法解决动态统计子树权和的问题。类似于线段树，将区间分成小段，方便计算权和。举个栗子，将a数组构造成树状数组c。如果a

忘是亡心i/ 2022年07月26日 08:44/ 0 赞/ 245 阅读

相关 LeetCode:Reverse String

最近新加的一道题，用C++秒过，12秒，反转字符串，思路很简单，一种暴力方法就用直接用一个新的字符串存储，然后一个一个从后往前遍历旧的字符串。第二种就是原地用2个指针从两端往中

矫情吗；*/ 2022年07月17日 04:37/ 0 赞/ 50 阅读

相关 [Leetcode]Reverse String

Write a function that takes a string as input and returns the string reversed. Example:

痛定思痛。/ 2022年06月10日 05:15/ 0 赞/ 172 阅读

相关 344.Reverse String

/ Write a function that takes a string as input and returns the string reversed.

绝地灬酷狼/ 2022年06月09日 05:38/ 0 赞/ 114 阅读

相关树状数组

树状数组单点修改，单点查询洛谷oj :[点我][Link 1] 模板： include<iostream> include<cstdio>

心已赠人/ 2022年05月16日 05:17/ 0 赞/ 288 阅读

相关 Codeforces 1111E DP + 树状数组 + LCA + dfs序

题意：给你一颗树，有q次询问，每次询问给你若干个点，这些点可以最多分出m组，每组要满足两个条件：1：每组至少一个点，2：组内的点不能是组内其它点的祖先，问这样的分组能有多少个？

痛定思痛。/ 2021年12月12日 01:57/ 0 赞/ 287 阅读

相关 1430E - String Reversal (树状数组、队列)

[题目][Link 1] 思路：首先贪心一下，我们想要使得移动次数最小那肯定用前面离得近的元素去移动，所以我们用一个que来记录各个元素的位置，每使用完这个前面的位置的就

淩亂°似流年/ 2021年07月16日 16:31/ 0 赞/ 262 阅读