hdu 3415 Max Sum of Max-K-sub-sequence (单调队列)
hdu 3415 题意：给出n个整数，是一个环（也就是a[n]右边是a[1]）求一段长度不超过k的数使得和最大，问最大和是多少并给出这段数的位置。
思路：为了处理环，先把n个数复制一下就好，然后求前缀和sum[i]
由于区间[l,r]的和可以用前缀和表示为sum[r]-sum[l-1]
因此在区间长度小于等于k的前提下，我要求sum[r]-sum[l-1]的最大值，如果我们考虑把端点r固定，那么就是要求[l-1,r-1]中的sum的最小值。
因此我们考虑用单调队列来维护sum[i-k]到sum[i-1]的最小值。
我们的做法是：枚举区间右端点i，同时用单调队列维护i之前的k个数[i-k,i-1]的最小值。
由于要求“If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.”，因此从后面出队的判断条件是严格的sum[dq.back()]>sum[i-1]
/* ***********************************************
Author :111qqz
Created Time :2016年08月05日 星期五 18时02分36秒
File Name :code/hdu/3415.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <stack>
8#include <set>
9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <ctime>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7int a[N],sum[N];
8int n,k;
9int on;
10deque<int>dq;
11inline bool read(int &num)
12{
13 char in;
14 bool ISN = false;
15 in=getchar();
16 if (in==EOF) return false;
17 while (in!='-'&&(in<'0'||in>'9')) in=getchar();
18 if (in=='-') ISN = true,num=0;
19 else num=in-'0';
20 while (in=getchar(),in>='0'&&in<='9'){
21 num*=10,num+=in-'0';
22 }
23 if (ISN) num=-num;
24 return true;
25}
26int main()
27{
28#ifndef ONLINE_JUDGE
29 freopen("code/in.txt","r",stdin);
30#endif
1 int T;
2 //scanf("%d",&T);
3 read(T);
4 while (T--)
5 {
6 scanf("%d%d",&n,&k);
7// read(n);
8// read(k);
9 on = n ;
10 sum[0] = 0 ;
11 for ( int i = 1 ; i <= n ; i++){
12 scanf("%d",&a[i]);
13 // read(a[i]);
14 a[i+n] = a[i];
15 }
16 n = n+k-1;
17 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + a[i];
18// for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "; cout<<endl;
19// for ( int i = 1 ; i <= n ; i++) cout<<sum[i]<<" "; cout<<endl;
20 dq.clear();
21 int ans = -inf;
22 int l,r;
23 for ( int i = 1 ; i <= n ; i++) //枚举最后一个元素
24 {
25 while (!dq.empty()&&dq.front()<i-k) dq.pop_front(); //仍然是维护k个，不过由于前缀和的性质，当前要入队的元素是i-1。
26 while (!dq.empty()&&sum[dq.back()]>sum[i-1]) dq.pop_back();
27 dq.push_back(i-1);
28 if (sum[i]-sum[dq.front()]>ans)
29 {
30 ans = sum[i] - sum[dq.front()];
31 l = dq.front()+1;
32 r = i ;
33 }
34 }
35 if (r>on) r%=on;
36 printf("%d %d %d\n",ans,l,r);
37 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}