BZOJ 3192 删除物品(树状数组)

时间:2022-06-15 05:07:42

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=3192

题意:(1)一共有N个物品,堆成M堆。

(2)所有物品都是一样的,但是它们有不同的优先级。
(3)你只能够移动某堆中位于顶端的物品。
(4)你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的,可以直接将之删除而不用移动。
(5)求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

(6)这是一个比较难解决的问题,这里你只需要解决一个比较简单的版本: 不会有两个物品有着相同的优先级,且M=2。

思路:将两堆放在一起,设分界点为mid。由于删除时只能按照编号降序依次删除,则首先将数字排序并记录数字的位置。从大到小删除。根据每个数字的位置计算删除每个数字的移动次数。

struct node
{
    int x,id;
};

node a[N];
int n,b[N],n1,n2;

void add(int x)
{
    while(x<N) b[x]++,x+=x&-x;
}

int get(int x)
{
    int ans=0;
    while(x) ans+=b[x],x-=x&-x;
    return ans;
}

int cmp(node a,node b)
{
    return a.x<b.x;
}

int main()
{
    RD(n1,n2);
    int i;
    for(i=n1;i>=1;i--) RD(a[i].x);
    for(i=n1+1;i<=n1+n2;i++) RD(a[i].x);
    n=n1+n2;
    FOR1(i,n) a[i].id=i;
    sort(a+1,a+n+1,cmp);
    i64 ans=0;
    int mid=n1,x;
    for(i=n;i>=1;i--)
    {
        x=a[i].id;
        if(x<=mid)
        {
            ans+=mid-x-(get(mid)-get(x));
            mid=x;
            add(x);
        }
        else
        {
            ans+=x-1-mid-(get(x-1)-get(mid));
            mid=x-1;
            add(x);
        }
    }
    PR(ans);
}

BZOJ 3192 删除物品(树状数组)的更多相关文章

  1. &lbrack;JLOI2013&rsqb;删除物品 树状数组

    当时考试时间剩下太短了然后就挂掉了..其实是个简单的数据结构. 话说一看最小还以为是动规呢.. 将两堆头对头排.比如样例就是 541|273 因为是必须有优先级次序,依次拿的话,看优先级大小相邻的两个 ...

  2. &lbrack;bzoj3192&rsqb;&lbrack;JLOI2013&rsqb;删除物品&lpar;树状数组&rpar;

    3192: [JLOI2013]删除物品 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 872  Solved: 508[Submit][Status ...

  3. bzoj 3192 删除物品

    Written with StackEdit. Description 箱子再分配问题需要解决如下问题: (1)一共有\(N\)个物品,堆成\(M\)堆. (2)所有物品都是一样的,但是它们有不同的优 ...

  4. Bzoj 2789&colon; &lbrack;Poi2012&rsqb;Letters 树状数组&comma;逆序对

    2789: [Poi2012]Letters Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 278  Solved: 185[Submit][Stat ...

  5. BZOJ 4361 isn &vert; DP 树状数组

    链接 BZOJ 4361 题面 给出一个长度为n的序列A(A1,A2...AN).如果序列A不是非降的,你必须从中删去一个数, 这一操作,直到A非降为止.求有多少种不同的操作方案,答案模10^9+7. ...

  6. BZOJ&period;1901&period;Dynamic Rankings&lpar;树状数组套主席树&lpar;动态主席树&rpar;&rpar;

    题目链接 BZOJ 洛谷 区间第k小,我们可以想到主席树.然而这是静态的,怎么支持修改? 静态的主席树是利用前缀和+差分来求解的,那么对于每个位置上的每棵树看做一个点,拿树状数组更新. 还是树状数组的 ...

  7. bzoj 2434 AC自动机&plus;树状数组

    2434: [Noi2011]阿狸的打字机 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 3493  Solved: 1909[Submit][Sta ...

  8. BZOJ 2727 双十字(树状数组)

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2727 题意: 思路:思路来自这里.首先对于每个位置(i,j)用C[i][j]表示该位置同 ...

  9. BZOJ 3333 排队计划 树状数组&plus;线段树

    题目大意:给定一个序列.每次选择一个位置,把这个位置之后全部小于等于这个数的数抽出来,排序,再插回去,求每次操作后的逆序对数 首先我们每一次操作 对于这个位置前面的数 因为排序的数与前面的数位置关系不 ...

  10. BZOJ&period;4361&period;isn&lpar;DP 树状数组 容斥&rpar;

    题目链接 长度为\(i\)的不降子序列个数是可以DP求的. 用\(f[i][j]\)表示长度为\(i\),结尾元素为\(a_j\)的不降子序列个数.转移为\(f[i][j]=\sum f[i-1][k ...

随机推荐

  1. mysql5&period;7忘记密码

    注意:mysql5.7 user表密码字段由password改为authentication_string 1.service mysql stop 2.mysqld_safe --skip-gran ...

  2. jquery resize事件增强版

    /* * jQuery resize event - v1.1 - 3/14/2010 * http://benalman.com/projects/jquery-resize-plugin/ * * ...

  3. Math 对象 识记

    Math 对象用于执行数学任务. 1.使用 Math 的属性和方法的语法: var pi_value=Math.PI; var sqrt_value=Math.sqrt(15); 注释:Math 对象 ...

  4. Android 带你玩转实现游戏2048 其实2048只是个普通的控件

    转载请标明出处:http://blog.csdn.net/lmj623565791/article/details/40020137,本文出自:[张鸿洋的博客] 1.概述 博主本想踏入游戏开放行业,无 ...

  5. 动态规划dp

    一.概念:动态规划dp:是一种分阶段求解决策问题的数学思想. 总结起来就一句话:大事化小,小事化了 二.例子 1.走台阶问题 F(10):10级台阶的走法数量 所以:F(10)=F(9)+F(8) F ...

  6. es 模块的基础知识,深度了解

    // 一模块的基础知识 /** * export :用于模块输出的出口 * import :文件引入的入口 */ // 1,第一种方式使用export方式输出 var a = 'a'; var b = ...

  7. PHP 数字金额转换成中文大写金额的函数 数字转中文

    /** *数字金额转换成中文大写金额的函数 *String Int $num 要转换的小写数字或小写字符串 *return 大写字母 *小数位为两位 **/ function num_to_rmb($ ...

  8. 记录git rebase用法

    git 是基于文件系统的版本管理工具,文档和详细介绍可以查看git 一.git commit --amend 如果你对文件做了修改需要和上一次的修改合并为一个change git add . git ...

  9. POS开发问题 - 跳转页面更新,返回还原旧数据

    问题描述:由于需求的需要,路由需要加上缓存 <keep-alive> ,还要实现跳转就初始化,返回就还原的需求.意思就是:页面 A 跳转到页面 B ,页面 B 要初始化数据,但是 页面 B ...

  10. Windows消息钩取

    @author: dlive @date: 2016/12/19 0x01 SetWindowsHookEx() HHOOK SetWindowsHookEx( int idHook, //hook ...