热门标签 | 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


推荐阅读
  • NOIP2000的单词接龙问题与常见的成语接龙游戏有异曲同工之妙。题目要求在给定的一组单词中,从指定的起始字母开始,构建最长的“单词链”。每个单词在链中最多可出现两次。本文将详细解析该题目的解法,并分享学习过程中的心得体会。 ... [详细]
  • 在Android平台上,视频监控系统的优化与应用具有重要意义。尽管已有相关示例(如http:www.open-open.comlibviewopen1346400423609.html)展示了基本的监控功能实现,但若要提升系统的稳定性和性能,仍需进行深入研究和优化。本文探讨了如何通过改进算法、优化网络传输和增强用户界面来提高Android视频监控系统的整体效能,以满足更复杂的应用需求。 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • ### 摘要`mkdir` 命令用于在指定位置创建新的目录。其基本格式为 `mkdir [选项] 目录名称`。通过该命令,用户可以在文件系统中创建一个或多个以指定名称命名的文件夹。执行此操作的用户需要具备相应的权限。此外,`mkdir` 还支持多种选项,如 `-p` 用于递归创建多级目录,确保路径中的所有层级都存在。掌握这些基本用法和选项,有助于提高在 Linux 系统中的文件管理效率。 ... [详细]
  • 在 POJ1651 的乘法谜题挑战中,如果选手按相反顺序选择卡片,即先选 50,再选 20,最后选 1,则最终得分会有所不同。题目要求输入的第一行包含... 改写后的摘要:在 POJ1651 的乘法谜题挑战中,如果选手按照逆序选取卡片,例如依次选择 50、20 和 1,最终的得分将发生变化。题目首先要求输入的第一行包括... ... [详细]
  • AngularJS 进阶指南:第三部分深入解析
    在本文中,我们将深入探讨 AngularJS 的指令模型,特别是 `ng-model` 指令。`ng-model` 指令用于将 HTML 元素与应用程序数据进行双向绑定,支持多种数据类型验证,如数字、电子邮件地址和必填项检查。此外,我们还将介绍如何利用该指令优化表单验证和数据处理流程,提升开发效率和用户体验。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 在探讨Hibernate框架的高级特性时,缓存机制和懒加载策略是提升数据操作效率的关键要素。缓存策略能够显著减少数据库访问次数,从而提高应用性能,特别是在处理频繁访问的数据时。Hibernate提供了多层次的缓存支持,包括一级缓存和二级缓存,以满足不同场景下的需求。懒加载策略则通过按需加载关联对象,进一步优化了资源利用和响应时间。本文将深入分析这些机制的实现原理及其最佳实践。 ... [详细]
  • Android中将独立SO库封装进JAR包并实现SO库的加载与调用
    在Android开发中,将独立的SO库封装进JAR包并实现其加载与调用是一个常见的需求。本文详细介绍了如何将SO库嵌入到JAR包中,并确保在外部应用调用该JAR包时能够正确加载和使用这些SO库。通过这种方式,开发者可以更方便地管理和分发包含原生代码的库文件,提高开发效率和代码复用性。文章还探讨了常见的问题及其解决方案,帮助开发者避免在实际应用中遇到的坑。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • 本文详细介绍了使用 Python 进行 MySQL 和 Redis 数据库操作的实战技巧。首先,针对 MySQL 数据库,通过 `pymysql` 模块展示了如何连接和操作数据库,包括建立连接、执行查询和更新等常见操作。接着,文章深入探讨了 Redis 的基本命令和高级功能,如键值存储、列表操作和事务处理。此外,还提供了多个实际案例,帮助读者更好地理解和应用这些技术。 ... [详细]
  • 在 CentOS 6.5 系统上部署 VNC 服务器的详细步骤与配置指南
    在 CentOS 6.5 系统上部署 VNC 服务器时,首先需要确认 VNC 服务是否已安装。通常情况下,VNC 服务默认未安装。可以通过运行特定的查询命令来检查其安装状态。如果查询结果为空,则表明 VNC 服务尚未安装,需进行手动安装。此外,建议在安装前确保系统的软件包管理器已更新至最新版本,以避免兼容性问题。 ... [详细]
  • 资源管理器的基础架构包括三个核心组件:1)资源池,用于将CPU和内存等资源分配给不同的容器;2)负载组,负责承载任务并将其分配到相应的资源池;3)分类函数,用于将不同的会话映射到合适的负载组。该系统提供了两种主要的资源管理策略。 ... [详细]
  • POJ3669题目解析:基于广度优先搜索的详细解答
    POJ3669(http://poj.org/problem?id=3669)是一道典型的广度优先搜索(BFS)问题。由于陨石的降落具有时间属性,导致地图状态会随时间动态变化。因此,可以利用结构体来记录每个陨石的降落时间和位置,从而有效地进行状态更新和路径搜索。 ... [详细]
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社区 版权所有