Problem Description

Given a circle sequence $A[1],A[2],A[3],\dots A[n]$. Circle sequence means the left neighbor of $A[1]$ is $A[n]$ , and the right neighbor 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 \leq T \leq 100)$ which means the number of test cases.
Then $T$ lines follow, each line starts with two integers $N$ , $K(1 \leq N \leq 100000 , 1 \leq K\leq 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

大意是找出一个循环数组的和最大的长度不大于 $k$ 的子序列。这里涉及到一个移动窗口并且要找到最大值,会很明显的想到单调队列。子序列的和可以用末尾元素的前缀和减去开头元素前者的前缀和来表示。找到最大的子序列的和,可以通过枚举末尾元素并用其前缀和减去相应的在长度为 $k$ 的窗口内出现的最小的前缀和,取最大值。

另外,循环数组可以通过在原数组末尾加上 $k - 1$ 个元素来实现。

单调队列

这个在前面的博客也有写过。具体思想就是:

  1. 若队列为空,将A[i]从对队尾入队。
  2. 若队列不为空,将比A[i]大的元素从队尾弹出,然后把A[i]入队。
  3. 若队列不为空且A[i]大于队尾,则直接从队尾把A[i]入队。

一个实现单调增的单调队列如下:

void min(){
    int front = 1, tail = 0;
    for (int i = 0; i < k - 1; i++) {
        while (front <= tail && a[i] < a[que[tail]])
            tail--;
        tail++;
        que[tail] = i;
    }
    for (int i = k - 1; i < n; i++) {
        while (front <= tail && a[i] < a[que[tail]]) {
            tail--;
        }
        tail++;
        que[tail] = i;
        while (k < i - que[front] + 1) {
            front++;
        }
        if (i == k - 1) // 取出头元素即最小的那个元素
            cout << a[que[front]];
        else cout << " " << a[que[front]];
    }
}

要注意的是 que[] 数组中存的是相应位的下标。

针对本题

实现这个题目需要对以上实现的单调队列进行一定的修改。

首先,我们在找最小的前缀和时不一定要满足此时窗口内元素一定满足了长度到达了 $k$,所以第一个 for 循环没有存在的必要,直接将两个循环合并即可。

其次,来看输出要求。

  1. 如果子序列最大值均相同,则输出最小的首元素。这个可以通过在最后循环时候判断如果相同且首元素更小则更换答案来实现。
  2. 如果子序列最大值与最小的首元素均相同,则输出长度更小的。这个可以在单调队列运行时完成。因为后进入序列的一定是更加靠后的元素,所以在判断新进元素与单调队列原有元素的大小关系时,将原有的判断关系(小于)更改为不大于。这样可以保证有相同的元素出现时,单调队列里出现的元素一定是后进入单调队列的元素,即可以使子序列长度更小。

最后,还要注意因为前缀和而改变的单调队列窗口下标的改变。$subSum[i][j] = sum[j] - sum[i - 1]$,所以窗口的下标范围应该是 $i - k$ ~ $i - 1$。

通过以上的一些分析,我们可以得到以下的AC代码:

#include <iostream>
#define MAXN 1000005
using namespace std;
int a[MAXN * 2];
int que[MAXN]; // 单调队列
int sum[MAXN * 2];
int n, k;
int begin;

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (i <= k - 1) {
                a[i + n] = a[i];
            }
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = 1; i <= k - 1; i++) {
            sum[n + i] = sum[n + i - 1] + a[n + i];
        }
        int ansMax = INT32_MIN;
        int nowAns;
        int ansHead = 0;
        int ansTail = 0;
        int front = 1, tail = 0;        
        for (int i = 1; i <= n + k - 1; i++) {
            while (front <= tail && sum[i - 1] <= sum[que[tail]]) {
                tail--;
            }
            tail++;
            que[tail] = i - 1;
            while (k < i - que[front]) {
                front ++;
            }
            nowAns = sum[i] - sum[que[front]];
            if (nowAns > ansMax || (nowAns == ansMax && (que[front])% n + 1 < ansHead %n + 1)) {
                ansMax = nowAns;
                ansHead = que[front];
                ansTail = i;
            }
        }
        cout << ansMax << " " << ansHead % n + 1 << " " << (ansTail - 1) % n + 1 << endl;
    }
}

审题不规范,罚时两行泪。