题目链接:Click
here~~
上次比赛的一道题,可以用单调队列做。
题意:
给你一个n项的序列,每次可以把序列的首项移动到末尾,显然一共可以构成 n 种序列,问一共有多少种序列满足条件:序列的前 i 项和都大于等于0(i:1~n)。
解题思路:
开一个 2*n 的数组,后面 n 项复制前面 n 项。这样,每个长度为 n 的区间都代表一种序列(这也是循环序列的一般做法吧)。
然后,数组中的值 sum[i] 记录前面 i 项的和 (1 ~ i)。
这样,我们在考虑以 k 为起点的区间时,只要把 sum[i] - sum[k-1] 便可得到以 k 为起点的序列的前 j 项和(j=i-k+1)。
如果当前区间中的最小的 sum[i] 都满足 sum[i] - sum[k-1] >= 0,那么区间中的所有值也一定满足此条件。
问题从而转化成了如何求滚动区间中的最小值,我们不难想到单调队列的做法。复杂度O(n)。
#include <stdio.h>
const int M = 1000002<<1; //2倍空间
int sum[M],q[M]; //sum记录前i项和,q记录队列中元素的位置
int head,rear,ans,n;
void In_queue(int i)
{
while(head <= rear && sum[i] <= sum[ q[rear] ])//删除队中大于等于它的元素
rear--;
q[++rear] = i;
}
void Out_queue(int i)
{
if(q[head] < i - n + 1) //如果队首不在区间范围内,删除
head++;
}
int main()
{
while(scanf("%d",&n),n)
{
ans = 0 , head = 0 , rear = -1; //初始队列指针
for(int i=1;i<=n;i++)
{
scanf("%d",&sum[i]);
sum[i+n] = sum[i];
}
for(int i=2;i < 2*n ;i++)
sum[i] += sum[i-1];
for(int i=1;i < n ;i++)
In_queue(i); //入队
for(int i=n;i < 2*n ;i++) //依次求区间[i-n+1,i]中的最小值
{
In_queue(i); //入队
Out_queue(i); //出队
if(sum[ q[head] ] - sum[i-n] >= 0) //如果最小值都大于等于0,计数
ans++;
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭电ACM2000-2099题的解题报告
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh