题目链接: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 删除物品(树状数组)的更多相关文章
-
[JLOI2013]删除物品 树状数组
当时考试时间剩下太短了然后就挂掉了..其实是个简单的数据结构. 话说一看最小还以为是动规呢.. 将两堆头对头排.比如样例就是 541|273 因为是必须有优先级次序,依次拿的话,看优先级大小相邻的两个 ...
-
[bzoj3192][JLOI2013]删除物品(树状数组)
3192: [JLOI2013]删除物品 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 872 Solved: 508[Submit][Status ...
-
bzoj 3192 删除物品
Written with StackEdit. Description 箱子再分配问题需要解决如下问题: (1)一共有\(N\)个物品,堆成\(M\)堆. (2)所有物品都是一样的,但是它们有不同的优 ...
-
Bzoj 2789: [Poi2012]Letters 树状数组,逆序对
2789: [Poi2012]Letters Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 278 Solved: 185[Submit][Stat ...
-
BZOJ 4361 isn | DP 树状数组
链接 BZOJ 4361 题面 给出一个长度为n的序列A(A1,A2...AN).如果序列A不是非降的,你必须从中删去一个数, 这一操作,直到A非降为止.求有多少种不同的操作方案,答案模10^9+7. ...
-
BZOJ.1901.Dynamic Rankings(树状数组套主席树(动态主席树))
题目链接 BZOJ 洛谷 区间第k小,我们可以想到主席树.然而这是静态的,怎么支持修改? 静态的主席树是利用前缀和+差分来求解的,那么对于每个位置上的每棵树看做一个点,拿树状数组更新. 还是树状数组的 ...
-
bzoj 2434 AC自动机+树状数组
2434: [Noi2011]阿狸的打字机 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 3493 Solved: 1909[Submit][Sta ...
-
BZOJ 2727 双十字(树状数组)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2727 题意: 思路:思路来自这里.首先对于每个位置(i,j)用C[i][j]表示该位置同 ...
-
BZOJ 3333 排队计划 树状数组+线段树
题目大意:给定一个序列.每次选择一个位置,把这个位置之后全部小于等于这个数的数抽出来,排序,再插回去,求每次操作后的逆序对数 首先我们每一次操作 对于这个位置前面的数 因为排序的数与前面的数位置关系不 ...
-
BZOJ.4361.isn(DP 树状数组 容斥)
题目链接 长度为\(i\)的不降子序列个数是可以DP求的. 用\(f[i][j]\)表示长度为\(i\),结尾元素为\(a_j\)的不降子序列个数.转移为\(f[i][j]=\sum f[i-1][k ...
随机推荐
-
mysql5.7忘记密码
注意:mysql5.7 user表密码字段由password改为authentication_string 1.service mysql stop 2.mysqld_safe --skip-gran ...
-
jquery resize事件增强版
/* * jQuery resize event - v1.1 - 3/14/2010 * http://benalman.com/projects/jquery-resize-plugin/ * * ...
-
Math 对象 识记
Math 对象用于执行数学任务. 1.使用 Math 的属性和方法的语法: var pi_value=Math.PI; var sqrt_value=Math.sqrt(15); 注释:Math 对象 ...
-
Android 带你玩转实现游戏2048 其实2048只是个普通的控件
转载请标明出处:http://blog.csdn.net/lmj623565791/article/details/40020137,本文出自:[张鸿洋的博客] 1.概述 博主本想踏入游戏开放行业,无 ...
-
动态规划dp
一.概念:动态规划dp:是一种分阶段求解决策问题的数学思想. 总结起来就一句话:大事化小,小事化了 二.例子 1.走台阶问题 F(10):10级台阶的走法数量 所以:F(10)=F(9)+F(8) F ...
-
es 模块的基础知识,深度了解
// 一模块的基础知识 /** * export :用于模块输出的出口 * import :文件引入的入口 */ // 1,第一种方式使用export方式输出 var a = 'a'; var b = ...
-
PHP 数字金额转换成中文大写金额的函数 数字转中文
/** *数字金额转换成中文大写金额的函数 *String Int $num 要转换的小写数字或小写字符串 *return 大写字母 *小数位为两位 **/ function num_to_rmb($ ...
-
记录git rebase用法
git 是基于文件系统的版本管理工具,文档和详细介绍可以查看git 一.git commit --amend 如果你对文件做了修改需要和上一次的修改合并为一个change git add . git ...
-
POS开发问题 - 跳转页面更新,返回还原旧数据
问题描述:由于需求的需要,路由需要加上缓存 <keep-alive> ,还要实现跳转就初始化,返回就还原的需求.意思就是:页面 A 跳转到页面 B ,页面 B 要初始化数据,但是 页面 B ...
-
Windows消息钩取
@author: dlive @date: 2016/12/19 0x01 SetWindowsHookEx() HHOOK SetWindowsHookEx( int idHook, //hook ...