KIDx的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3415
题意:给出一个有n个数字的环状序列(其中每个数在-1000到1000之间,且n<=100000),求一个和最大的连续子序列。(要求这个连续序列长度小于等于K)
单调队列基本模型:保持队列中元素单调递增(或递减),可以两头删除,只能从队尾插入新元素,队首q[head]为当前最优区间头,队列存的是下标。
基本思路:由于是环,补足2*n个数, 预处理出前2*n项和,枚举区间尾i, 如果当前区间尾是i,有最优区间头q[head],那么sum[i]-sum[q[head]-1]就是区间[q[head], i]的和。
为何对于当前区间尾i最优区间头是q[head]?这就是删除队列尾的功劳了:i显然可能是当前或者以后的最优区间头,所以需要插入,而q[tail-1]是队列最后一个元素,如果区间[q[tail-1], i-1]的和小于0,要让q[tail-1]作为区间头的话,必然让和更小了,所以i是更好的区间头,于是把所有劣解q[tail-1]去掉,也就是出队列,反之q[tail-1]必然比i更优,所以说队首就是当前区间的最优的区间头了
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define M 200005
#define inf 0x3fffffff
int q[M], sum[M];
int cal (int a, int b) { return sum[b] - sum[a-1]; }
int main()
{
int t, n, k, i;
scanf("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &k);
for (i = 1; i <= n; i++)
scanf ("%d", sum+i);
for (i = n+1; i <= 2*n; i++)
sum[i] = sum[i-n];
for (i = 2; i <= 2*n; i++) //预处理前2*n项和(其实n+k即可)
sum[i] += sum[i-1];
int head = 0, tail = 0, maxs = -inf, a, b;
for (i = 1; i <= 2*n; i++) //枚举区间尾i
{
//把劣解出队列
while (tail > head && cal(q[tail-1], i-1) < 0) --tail;
q[tail++] = i;
//当前最优区间头q[head],计算区间[q[head], i]的和
int tp = cal(q[head], i);
if (tp > maxs)
{
maxs = tp;
a = q[head];
b = i;
}
//超出长度,q[head]已经不能为下一个区间尾所用就出队列
while (tail > head && i - q[head] + 1 >= k) ++head;
}
if (b > n) b -= n; //b可能大于n而不满足题意
printf ("%d %d %d\n", maxs, a, b);
}
return 0;
}
分享到:
相关推荐
### DP的单调队列优化详解 #### 一、单调队列简介 单调队列是一种特殊的数据结构,主要用于处理滑动窗口中的最值问题。在算法竞赛中,尤其是在DP(动态规划)问题中,通过利用单调队列可以有效地优化时间复杂度。 ...
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
标题中的“HDU数据库单元原理(Oracle)”是指在华为的HLR(Home Location Register)系统中,关于数据库单元的设计和实现原理,特别是基于Oracle数据库系统的部分。HLR是移动通信网络中的核心组件,用于存储用户的...
其中一类查询要求 更新 数组 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]
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
Nim 游戏的分析可以使用 Nim-Sum 概念,Nim-Sum 是指将多个数字按照一定的规则进行组合的结果。定理一表明,对于 Nim 游戏的某个位置,当且仅当它各部分的 Nim-Sum 等于 0 时,则当前位于必败点。 组合博弈是研究...
《ACM HDU 2000-2099 解题报告 杭电 ACM》是一份详尽的编程竞赛解题集,主要涵盖了杭电(Hangzhou Dianzi University)在线判题系统(HDU OJ)上的2000至2099号题目。这份解题报告是针对参与ACM/ICPC(国际大学生...
在编程竞赛的世界里,HDU(Hangzhou Dianzi University)举办的Multi-University Training Contest一直备受关注,尤其是2019年的第六场赛事,更是吸引了众多参赛者一展才华。这个名为"2019 Multi-University ...
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...
在IT行业中,"Number Sequence"通常指的是在特定系统或应用中用于生成自动递增或递减的数字序列。这些序列可以用于唯一标识记录、订单号、发票号等,确保数据的唯一性和可追踪性。在Microsoft Dynamics AX(现称为...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
教你小小JAVA爬虫爬到HDU首页(只为学习)-附件资源
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh