/*AC
思路:使用sum[i]存储前i个序列之和,队列中存储区间内出现过最小序列和,这样只需要sum[i]前去最小序列和即可。
*/
#include <iostream>
using namespace std;
const int nMax = 100010;
const int INF = 0x7fffffff;
int A[nMax];
int sum[2 * nMax];//这里需要增倍
struct Queue
{
int pos;
int v;
Queue(){}
Queue(int pos, int v): pos(pos), v(v){}
}queue[2 * nMax];
int front, rear;
int t, n, k;
int main()
{
//freopen("e://data.txt", "r", stdin);
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &k);
sum[0] = 0;
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &A[i]);
sum[i] = sum[i - 1] + A[i];
}
for(int i = n + 1; i <= n + k; ++ i)
sum[i] = sum[i - 1] + A[i - n];
front = rear = 0;
int Max = -INF;
int l, r;
queue[front ++] = Queue(0, 0);//队列中存储最小元素和
for(int i = 1; i <= n + k; ++ i)
{
while(rear < front && (i - queue[rear].pos) > k)//这里做了改动
rear ++;
if(sum[i] - queue[rear].v > Max)//把结果运算放到了前面,这样更好一些
{
Max = sum[i] - queue[rear].v;
l = queue[rear].pos + 1;
r = i;
}
while(rear < front && queue[front - 1].v > sum[i])
front --;
queue[front ++] = Queue(i, sum[i]);
}
printf("%d %d %d\n", Max, (l - 1) % n + 1, (r - 1) % n + 1);
}
return 0;
}
/*AC
错误出在①处
#include <iostream>
using namespace std;
const int nMax = 100010;
int A[nMax];
int sum[2 * nMax];//这里需要增倍
struct Queue
{
int pos;
int v;
Queue(){}
Queue(int pos, int v): pos(pos), v(v){}
}queue[2 * nMax];
int front, rear;
int t, n, k;
int main()
{
//freopen("e://data.txt", "r", stdin);
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &k);
sum[0] = 0;
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &A[i]);
sum[i] = sum[i - 1] + A[i];
}
for(int i = n + 1; i <= n + k; ++ i)
sum[i] = sum[i - 1] + A[i - n];
front = rear = 0;
int Max = sum[1];//初始化
int l, r;
l = r = 1;
queue[front ++] = Queue(0, 0);//队列中存储最小元素和
for(int i = 1; i < n + k; ++ i)
{
while(rear < front && queue[front - 1].v > sum[i])
front --;
queue[front ++] = Queue(i, sum[i]);
while(rear < front && (i + 1 - queue[rear].pos) > k)//①这个需要在if之前进行判断
rear ++;
if(sum[i + 1] - queue[rear].v > Max)//[queue[rear].pos, i + 1]的最大值
{
Max = sum[i + 1] - queue[rear].v;
l = queue[rear].pos + 1;
r = i + 1;
}
}
printf("%d %d %d\n", Max, (l - 1) % n + 1, (r - 1) % n + 1);
}
return 0;
}
*/
/*
第一次求解思路:
队列中存储长度在k之内的最大和,并存储l,r,在执行入队时候,需要遍历一次队列寻找出相连的元素,出队时判断l是否越界。
超时!
#include <iostream>
using namespace std;
const int INF = 0x7fffffff;
const int nMax = 100010;
int A[nMax];
struct Queue
{
int l, r;
int sum;
Queue(){}
Queue(int l, int r, int sum):l(l), r(r), sum(sum){}
}queue[nMax], ans;
int front, rear;
int t, n, k;
int main()
{
//freopen("e://data.txt", "r", stdin);
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &k);
int i;
for(i = 0; i < n; ++ i)
scanf("%d", &A[i]);
front = rear = 0;
int max;
int l;
for(i = 0; i < k; ++ i)
{
max = A[i];
l = i;
for(int j = rear; j < front; ++ j)
if(queue[j].r == i - 1 && queue[j].sum + A[i] > max)
{
max = queue[j].sum + A[i];
l = queue[j].l;
}
while(rear < front && queue[front - 1].sum < max)
front --;
queue[front ++] = Queue(l, i, max);
ans = queue[rear];
}
for(int j = i; j < n + k; ++ j)
{
while(rear < front && queue[rear].l < j - k + 1) rear ++;
i = j % n;
max = A[i];
l = i;
for(int j = rear; j < front; ++ j)
if(((i == 0 && queue[j].r == n - 1) || queue[j].r == i - 1) && queue[j].sum + A[i] > max)
{
max = queue[j].sum + A[i];
l = queue[j].l;
}
while(rear < front && queue[front - 1].sum < max)
front --;
queue[front ++] = Queue(l, i, max);
if(ans.sum < max)
ans = queue[rear];
}
printf("%d %d %d\n", ans.sum, ans.l + 1, ans.r + 1);
}
return 0;
}
*/
分享到:
相关推荐
示例 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]
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭电组合博弈课件
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
杭电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]++ } }
教你小小JAVA爬虫爬到HDU首页(只为学习)-附件资源
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。