热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BZOJ1112POI2008砖块Klo

1112:[POI2008]砖块KloDescriptionN柱砖,希望有连续K柱的高度是一样的.你可以选择以下两个动作1:从某柱砖的顶端拿一块砖出来,丢掉不要了.2:从仓库中拿出

1112: [POI2008]砖块Klo

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2194  Solved: 787
[Submit][Status][Discuss]

Description

N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

Input

第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

Output

最小的动作次数

Sample Input

5 3
3
9
2
3
1

Sample Output

2

HINT

原题还要求输出结束状态时,每柱砖的高度.本题略去.

Source

我们知道对于一个长度为k的序列,我们要花费最少的操作数就是把它们全部变为中位数

不要问我为什么,自己脑补一下即可

这时候我们就要拿出Treep去维护插入了删除操作,并查询区间中位数

我们不断维护一个长度为k的序列,每次往后移一位,把i-k删除,把i加入

最后算出花费即可   注意开longlong 坑死我了

技术分享图片技术分享图片
  1 #include 
  2 #define ll long long
  3 using namespace std;
  4 inline int read(){
  5     int x=0;int f=1;char ch=getchar();
  6     while(!isdigit(ch)) {if(ch==-) f=-1;ch=getchar();}
  7     while(isdigit(ch)) {x=x*10+ch-0;ch=getchar();}
  8     return x*f;
  9 }
 10 const int MAXN=1e5+10;
 11 int h[MAXN],n,cnt=0,tmp,root,m,k;
 12 ll ans,sum1,sum2;
 13 struct tree{
 14     int son[2],rnd,weight,siz;
 15     ll sum,v;
 16 }T[MAXN];
 17 inline void push_up(int root){
 18     T[root].siz=T[T[root].son[0]].siz+T[T[root].son[1]].siz+T[root].weight;
 19     T[root].sum=T[T[root].son[0]].sum+T[T[root].son[1]].sum+T[root].weight*T[root].v;
 20 }
 21 inline void leftrote(int &root){
 22     int x=T[root].son[1];T[root].son[1]=T[x].son[0];
 23     T[x].son[0]=root;push_up(root);push_up(x);root=x;
 24 }
 25 inline void rightrote(int &root){
 26     int x=T[root].son[0];T[root].son[0]=T[x].son[1];
 27     T[x].son[1]=root;push_up(root);push_up(x);root=x;
 28 }
 29 inline void insert(int &root,int vv){
 30     if(root==0){
 31         root=++cnt;T[root].v=T[root].sum=vv;
 32         T[root].weight=T[root].siz=1;
 33         T[root].rnd=rand();return;
 34     }
 35     T[root].sum+=vv;T[root].siz++;
 36     if(vv==T[root].v){
 37         T[root].weight++;
 38     }
 39     else if(vv<T[root].v){
 40         insert(T[root].son[0],vv);
 41         if(T[T[root].son[0]].rnd<T[root].rnd) rightrote(root);
 42     }
 43     else{
 44         insert(T[root].son[1],vv);
 45         if(T[T[root].son[1]].rnd<T[root].rnd) leftrote(root);
 46     }
 47 }
 48 inline void del(int &root,int vv){
 49     if(!root) return;
 50     if(T[root].v==vv){
 51         if(T[root].weight>1){
 52             T[root].weight--;T[root].sum-=vv;T[root].siz--;return;
 53         }
 54         if(T[root].son[0]*T[root].son[1]==0) root=T[root].son[0]+T[root].son[1];
 55         else if(T[T[root].son[0]].rnd1]].rnd) {rightrote(root);del(root,vv);}
 56         else {leftrote(root);del(root,vv);}
 57     }
 58     else if(vv>T[root].v){
 59         T[root].siz--;T[root].sum-=vv;del(T[root].son[1],vv);
 60     }
 61     else{
 62         T[root].siz--;T[root].sum-=vv;del(T[root].son[0],vv);
 63     }
 64 }
 65 inline void find(int root,int rank){
 66     if(!root) return;
 67     if(rank>T[T[root].son[0]].siz&&rank<=T[T[root].son[0]].siz+T[root].weight){  
 68         sum1+=(T[root].v*(rank-T[T[root].son[0]].siz-1)+T[T[root].son[0]].sum);
 69         sum2+=T[root].v*(T[root].weight+T[T[root].son[0]].siz-rank)+T[T[root].son[1]].sum;
 70         tmp=T[root].v;
 71     }
 72     else if(rank<=T[T[root].son[0]].siz){
 73         sum2+=(T[root].weight*T[root].v)+T[T[root].son[1]].sum;
 74         find(T[root].son[0],rank);
 75     }
 76     else{
 77         sum1+=(T[root].weight*T[root].v)+T[T[root].son[0]].sum;
 78         find(T[root].son[1],rank-T[T[root].son[0]].siz-T[root].weight);
 79     }
 80 }
 81 inline void getans(){
 82     sum1=sum2=0;
 83     find(root,m);
 84     //cout<
 85     ll t=1LL*(m-1)*tmp-sum1+sum2-1LL*(k-m)*tmp;
 86     ans=min(ans,t);
 87 }
 88 int main(){
 89     //freopen("All.in","r",stdin);
 90     //freopen("zh.out","w",stdout);
 91     n=read();k=read();m=(k+1)>>1;
 92     for(int i=1;i<=n;i++){
 93         h[i]=read();
 94     }
 95     ans=9000000000000;
 96     for(int i=1;i<=k;i++){
 97         insert(root,h[i]);
 98     }
 99     getans();
100     for(int i=k+1;i<=n;i++){
101         del(root,h[i-k]);insert(root,h[i]);
102         getans();
103     }
104     cout105     return 0;
106 }
View Code

BZOJ 1112 POI2008 砖块Klo


推荐阅读
  • egg实现登录鉴权(七):权限管理
    权限管理包含三部分:访问页面的权限,操作功能的权限和获取数据权限。页面权限:登录用户所属角色的可访问页面的权限功能权限:登录用户所属角色的可访问页面的操作权限数据权限:登录用户所属 ... [详细]
  • 本文提供了一个关于AC自动机(Aho-Corasick Algorithm)的详细解析与实现方法,特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念,还重点讲解了如何通过构建失败指针(fail pointer)来提高字符串匹配效率。 ... [详细]
  • 本文详细介绍如何在SSM(Spring + Spring MVC + MyBatis)框架中实现分页功能。包括分页的基本概念、数据准备、前端分页栏的设计与实现、后端分页逻辑的编写以及最终的测试步骤。 ... [详细]
  • selenium通过JS语法操作页面元素
    做过web测试的小伙伴们都知道,web元素现在很多是JS写的,那么既然是JS写的,可以通过JS语言去操作页面,来帮助我们操作一些selenium不能覆盖的功能。问题来了我们能否通过 ... [详细]
  • 本文由chszs撰写,详细介绍了Apache Mina框架的核心开发流程及自定义协议处理方法。文章涵盖从创建IoService实例到协议编解码的具体步骤,适合希望深入了解Mina框架应用的开发者。 ... [详细]
  • 本报告记录了嵌入式软件设计课程中的第二次实验,主要探讨了使用KEIL V5开发环境和ST固件库进行GPIO控制及按键响应编程的方法。通过实际操作,加深了对嵌入式系统硬件接口编程的理解。 ... [详细]
  • LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题,提供了C++语言的实现代码,并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • 深入解析Unity3D游戏开发中的音频播放技术
    在游戏开发中,音频播放是提升玩家沉浸感的关键因素之一。本文将探讨如何在Unity3D中高效地管理和播放不同类型的游戏音频,包括背景音乐和效果音效,并介绍实现这些功能的具体步骤。 ... [详细]
  • 本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程,不仅能够检验开发者对C++基础知识的掌握程度,还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能,如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]
  • Java连接MySQL数据库的方法及测试示例
    本文详细介绍了如何安装MySQL数据库,并通过Java编程语言实现与MySQL数据库的连接,包括环境搭建、数据库创建以及简单的查询操作。 ... [详细]
  • 本文探讨了如何使用Scrapy框架构建高效的数据采集系统,以及如何通过异步处理技术提升数据存储的效率。同时,文章还介绍了针对不同网站采用的不同采集策略。 ... [详细]
  • 3DSMAX制作超现实的体育馆模型
    这篇教程是向脚本之家的朋友介绍3DSMAX制作超现实的体育馆模型方法,教程制作出来的体育馆模型非常地不错,不过教程有点难度,需要有一定基础的朋友学习,推荐到脚本之家,喜欢的朋友可 ... [详细]
  • 本文介绍了如何在AngularJS应用中使用ng-repeat指令创建可单独点击选中的列表项,并详细描述了实现这一功能的具体步骤和代码示例。 ... [详细]
  • 在项目冲刺的最后一天,团队专注于软件用户界面的细节优化,包括调整控件布局和字体设置,以确保界面的简洁性和用户友好性。 ... [详细]
  • JavaScript 页面卸载事件详解 (onunload)
    当用户从页面离开时(如关闭页面或刷新页面),会触发 onunload 事件,此时可以执行预设的脚本。需要注意的是,不同的浏览器对 onunload 事件的支持程度可能有所不同。 ... [详细]
author-avatar
三个人999
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有