1 条题解
-
1
这道题和课上的OJ类似,只不过需要求的是最大的区间和,即 。一样的思路,先断环为链。然后维护单递减队列,用ans1和ans2分别记录最大心情值和此时开始汇报成绩的次序。注意下这里的ans1初始化一个较小值就好了~
参考代码
#include<iostream> using namespace std; int n, head = 1, tail, ans1=-100000,ans2; long long a[2000001], sum[2000001], q[2000001]; int main() { cin >> n; for ( int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 1; i <= n; i ++) a[i + n] = a[i]; for (int i = 1; i <= 2 * n; i ++) sum[i] = sum[i - 1] + a[i]; for (int k = 1; k <= n - 1 ; k ++) { while (head <= tail && sum[k] >= sum[q[tail]]) tail--; q[++tail] = k; } for (int k = 1; k <= n ; k ++) { if (head <= tail && k > q[head]) head++; while (head <= tail && sum[k + n - 1] >= sum[q[tail]]) tail--; q[++tail] = k + n - 1; if (sum[q[head]] - sum[k - 1] >= ans1) ans1=sum[q[head]] - sum[k - 1],ans2=k; } cout << ans2 << " " << ans1; return 0; }
- 1
信息
- ID
- 702
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 55
- 已通过
- 35
- 上传者