博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[POI2015]WIL-Wilcze doły
阅读量:6057 次
发布时间:2019-06-20

本文共 1013 字,大约阅读时间需要 3 分钟。

题目描述

给定一个长度为n的序列,你有一次机会选中一段连续的长度不超过d的区间,将里面所有数字全部修改为0。请找到最长的一段连续区间,使得该区间内所有数字之和不超过p。

输入格式:

第一行包含三个整数n,p,d(1<=d<=n<=2000000,0<=p<=10^16)。第二行包含n个正整数,依次表示序列中每个数w。

输出格式:

包含一行一个正整数,即修改后能找到的最长的符合条件的区间的长度。

题解:

发现,肯定要选择最多的d变成0,不然不优。并且,如果以i作为结尾,左端点为j的话,那么如果以i+1作为结尾,左端点不可能比j小。

所以,可以用一个双指针,维护L,R,

L、R为一个合法区间条件是,L~R的数的和,减去最大的长度为d的和,总和少于等于p

对于给定R,L不满足的时候,就把L右移即可。

至于L~R中长度等于d的最大的和,可以用一个单调队列维护。

复杂度O(n)

代码:

#include
using namespace std;typedef long long ll;const int N=2000000+10;int n,d;ll p;int ans;int q[N],l,r;ll sum[N],a[N];int main(){ scanf("%d%lld%d",&n,&p,&d); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } int L=1,R=1; l=1,r=0; q[++r]=d; for(R=d;R<=n;R++){ //cout<
<
p){ L++; while(l<=r&&q[l]-d+1
sum[q[r]]-sum[q[r]-d]) r--; q[++r]=R+1; } } printf("%d",ans); return 0;}

 

转载于:https://www.cnblogs.com/Miracevin/p/9656091.html

你可能感兴趣的文章
L2-019. 悄悄关注
查看>>
Zabbix 3.4.3之企业微信报警
查看>>
squid工作原理及源码包编译安装配置
查看>>
Python数据类型中的字典-创建和基本操作
查看>>
VMware虚拟化技术培训(10) 桌面虚拟化之二
查看>>
css自适应布局
查看>>
第 5 章 Nova - 031 - Start Instance 操作详解
查看>>
异步通知机制
查看>>
忘记支付密码了
查看>>
【C语言】【面试题】【笔试题】使用main函数实现一个整数计算器!
查看>>
Openstack之路(六)创建云主机实例
查看>>
《阿里巴巴常考面试题及汇总答案(上篇)》
查看>>
Python--闭包与装饰器
查看>>
zabbix监控告警Received empty response from Zabbix Agent Assuming that agent dropped connection
查看>>
初次接受C语言游戏程序感受
查看>>
nginx学习之反向代理负载均衡
查看>>
LayUI前端框架开发视频讲解
查看>>
Python学习记录-2016-11-26
查看>>
如何用源码安装ElasticSearch?
查看>>
Cisco路由器NAT的基础和应用场景
查看>>