[原创]HDU 3415 Max Sum of Max-K-sub-sequence [单调队列]【杂类】

2016-11-02 14:14:50 Tabris_ 阅读数：236

博客爬取于2020-06-14 22:42:54
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53007513

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3415
-------------------------------------.
Max Sum of Max-K-sub-sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7522 Accepted Submission(s): 2776

Problem Description
Given a circle sequence A[1],A[2],A[3]…A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.

Sample Input
4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1

Sample Output
7 1 3
7 1 3
7 6 2
-1 1 1

Author
shǎ崽@HDU

Source
HDOJ Monthly Contest – 2010.06.05

--------------------------------------.

题目大意：
给你一个成环的数列，让你寻找其中区间长度不大于k的区间最大和与 区间的起始位置和结束位置。

解题思路：

因为做的题目就是单调队列的专题 就没想算法

然后考虑成环的 所以要把区间变成2倍的 这样就有环了，，，

然后因为要取区间的和 而维护单调队列的时候也只是维护区间的左界 为了方便计算区间的值 所以把数组变成前缀和的形式

然后在维护的时候个人维护的是左界限的左一位的值 计算区间和比较容易

总的来说就是
枚举右界限 维护一下每次最优的左界线 然后把不符合结果的出队列就好了

附本题代码
--------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>

typedef long long int LL ;
using namespace std;

# define Rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

const int N = 2e6+5;
int a[N];
int p[N]; //单调队列 维护左界线下标

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        int n,k;
        scanf("%d%d",&n,&k);
        a[0]=0;
        Rep(i,1,n) scanf("%d",&a[i]),a[i+n]=a[i];

        n+=k-1;   //成环的话 因为最大的区间是K 座椅长度只需要n+k-1就行了
        Rep(i,2,n) a[i]+=a[i-1];

        int l=1,r=0,ml=-1,mr=-1,mx=-0x3f3f3f3f,tem=0;
        p[0]=p[++r]=0;//其实P[0] 是没有用的。。

        Rep(i,1,n){
            while(l<=r && p[l] < i-k) l++;  //不满足K的需要出队列

            tem = a[i]-a[p[l]];//  一定要在更新之前计算  否则结果可能因为负值出现错误
            if( tem > mx )    ml=p[l]+1,mr=i,mx=tem;

            while(l<=r && a[i] < a[ p[r] ]) r--;//更新最优解
            p[++r]=i;
        }

        n-=k-1;
        mr=(mr>n?mr-n:mr);//大于n的位置 处理一下
        printf("%d %d %d\n",mx,ml,mr);
    }
    return 0;
}