Gym - 101234J Zero Game (单调队列)
2024-09-02 07:58:34
题意:有一个长度为n的01序列,你可以移动k次,每次将一个数移到任意一个位置,求经过操作后区间连续最大的连续0的个数。
“移动”操作看似情况很复杂,不好讨论,但其实无非就两种情况:
一、移动的是1:显然最优的策略是将1移动到最边上(相当于“移走”),目的是将两段连续的0合并。
二、移动的是0:最优策略是将小堆中的0移动到大堆里,目的是增加大堆中0的个数。
这样一来,情况就简单多了,问题转化成了求“将一段连续区间中的0合并,然后剩下的操作次数用于把其他地方的0引进来”的最优解,即求$min(max\left\{\sum\limits_{i\leqslant j,cnt0(i,j)\leqslant k}(cnt0(i,j)+(k-cnt1(i,j)))\right\},cnt0(1,n))$,前缀和+单调队列搞一搞就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+;
char s[N];
int n,m,k,a[N],b[N],hd,tl;
struct P {int x,y;} q[N];
int main() {
scanf("%s",s+),n=strlen(s+);
for(int i=; i<=n; ++i)a[i]=a[i-]+(s[i]==''),b[i]=b[i-]+(s[i]=='');
scanf("%d",&m);
while(m--) {
int ans=;
scanf("%d",&k);
hd=tl=;
for(int j=,i=; j<=n; ++j) {
for(; i<=j&&b[j]-b[i-]>k; ++i);
for(; hd<tl&&q[hd].x<i-; ++hd);
P np= {j,a[j]-b[j]};
for(; hd<tl&&q[tl-].y>=np.y; --tl);
q[tl++]=np;
ans=max(ans,(a[j]-b[j])+(k-q[hd].y));
}
ans=min(ans,a[n]);
printf("%d\n",ans);
}
return ;
}
最新文章
- Hello session
- spring-mybatis jar下载地址
- css2----单行过长的省略处理
- hive中order by,sort by, distribute by, cluster by作用以及用法
- SQLServer错误:过程 sp_addextendedproperty,第 xxx 行对象无效。&#39;dbo.xxx.xxx&#39; 不允许有扩展属性,或对象不存在。
- activity属性_ _activity 属性说明
- 多元线性回归(Linear Regression with multiple variables)与最小二乘(least squat)
- Telnet客户端连接服务器,看不见字符,只显示横线
- legoblock秀上限
- redis数据结构HyperLogLog
- 畅通工程续--hdu1874
- Android高德地图开发具体解释
- Spring配置多数据源
- 第十五节:HttpContext五大核心对象的使用(Request、Response、Application、Server、Session)
- bmi
- (基础) 平方和与立方和 hdu2007
- layer 关闭当前弹出层
- 一个tomcat服务器上部署多个Web项目,不同域名访问
- Xamarin adventures – Differences between iOS simulator and device
- ARM汇编之MOV指令
热门文章
- Leetcode之动态规划(DP)专题-53. 最大子序和(Maximum Subarray)
- C++学习笔记-多态
- WIN32_FIND_DATA
- [转帖].MegaRAID SAS 9361-8i 开箱 极简测试
- Type类的使用
- # pycharm新建项目后运行按钮为灰色
- php 内存原理
- Win32汇编-创建窗体代码
- Bicolored RBS CodeForces - 1167D (括号)
- spring boot zuul集成kubernetes等第三方登录