hdu 4193 单调队列
2023-09-11 14:20:59 时间
题意是给你n个数 组成的环 求以一个数开头 的数列全部前缀都为非负数的数列的个数:
思路: 先扩展成2*n的数列 然后求出sum【i】表示前i项的和 对每一个i>.=n结尾的数列 仅仅要单调队列里的最小值大于等于sum【i-n】就满足情况(想想为什么) 对于单调队列 仅仅要维护长度大于等于n 递增的即可;
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int num[2001000],sum[2001000],id[2001000]; int main() { int n,i,j; while(~scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%d",&num[i]); num[i+n]=num[i]; } sum[0]=0; for(i=1;i<=n+n;i++) { sum[i]=sum[i-1]+num[i]; } int front=0,top=0; int t=0; for(i=1;i<n+n;i++) { while(front<top&&sum[i]<sum[id[top]]) top--; id[++top]=i; if(i>=n&&sum[id[front+1]]>=sum[i-n]) t++; while(id[top]-id[front+1]>=n) front++; } printf("%d\n",t); } return 0; }
相关文章
- 你真的了解:IIS连接数、IIS并发连接数、IIS最大并发工作线程数、应用程序池的队列长度、应用程序池的最大工作进程数吗
- PHP+Redis 定长队列(redis.call)
- laravel使用Redis邮件队列配置Supervisor实现异步发送邮件
- ECNUOJ 2149 华丽的队列
- 栈和队列,双端队列,如何用链表实现双端队列,如何用双端队列实现栈和队列
- 微服务轮子项目(31) -消息队列对比参照表
- 一则有趣的算法题:两个栈实现一个队列
- C++中TCP socket中接收和发送是不同的两个缓存区,接收远程数据时收到的数据都被填入接收缓冲区,什么时候接收什么时候清空,接收一个清空一个类似于队列。
- 数据结构队列顺序存储代码实现(C语言)
- linux 内核 工作队列
- 【C语言】利用队列的思维理解移位运算符和移位函数
- 力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
- 剑指Offer005之两个栈实现一个队列(相关话题:栈,队列)
- 消息队列
- 基于两端操作的循环队列的实现---怎么判断队满??
- Java 阻塞队列