Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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]
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月05日 星期五 18时02分36秒
4File Name :code/hdu/3415.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=2E5+7;
35int a[N],sum[N];
36int n,k;
37int on;
38deque<int>dq;
39inline bool read(int &num)
40{
41 char in;
42 bool ISN = false;
43 in=getchar();
44 if (in==EOF) return false;
45 while (in!='-'&&(in<'0'||in>'9')) in=getchar();
46 if (in=='-') ISN = true,num=0;
47 else num=in-'0';
48 while (in=getchar(),in>='0'&&in<='9'){
49 num*=10,num+=in-'0';
50 }
51 if (ISN) num=-num;
52 return true;
53}
54int main()
55{
56#ifndef ONLINE_JUDGE
57 freopen("code/in.txt","r",stdin);
58#endif
59
60 int T;
61 //scanf("%d",&T);
62 read(T);
63 while (T--)
64 {
65 scanf("%d%d",&n,&k);
66// read(n);
67// read(k);
68 on = n ;
69 sum[0] = 0 ;
70 for ( int i = 1 ; i <= n ; i++){
71 scanf("%d",&a[i]);
72 // read(a[i]);
73 a[i+n] = a[i];
74 }
75 n = n+k-1;
76 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + a[i];
77// for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "; cout<<endl;
78// for ( int i = 1 ; i <= n ; i++) cout<<sum[i]<<" "; cout<<endl;
79 dq.clear();
80 int ans = -inf;
81 int l,r;
82 for ( int i = 1 ; i <= n ; i++) //枚举最后一个元素
83 {
84 while (!dq.empty()&&dq.front()<i-k) dq.pop_front(); //仍然是维护k个，不过由于前缀和的性质，当前要入队的元素是i-1。
85 while (!dq.empty()&&sum[dq.back()]>sum[i-1]) dq.pop_back();
86 dq.push_back(i-1);
87 if (sum[i]-sum[dq.front()]>ans)
88 {
89 ans = sum[i] - sum[dq.front()];
90 l = dq.front()+1;
91 r = i ;
92 }
93 }
94 if (r>on) r%=on;
95 printf("%d %d %d\n",ans,l,r);
96 }
97
98#ifndef ONLINE_JUDGE
99 fclose(stdin);
100#endif
101 return 0;
102}