HDU 3415 Max Sum of Max-K-sub-sequence(单调队列)
/*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;}*/