建网站域名后怎样做,个人域名推荐,自动生成ui界面,开发公司送物业费的协议思路#xff1a;
a[]存愤怒值#xff1b;b[i]存以i结尾的#xff0c;窗口里的最大值#xff1b;c[i]存以i结尾的#xff0c;窗口里面包含✳的最大值。
#xff08;✳为新大象的位置#xff09;
例#xff1a;1 2 3 4 ✳ 5 6 7 8 9
则ans的计算公式b3b4c4c5c6b7b8b9…
思路
a[]存愤怒值b[i]存以i结尾的窗口里的最大值c[i]存以i结尾的窗口里面包含✳的最大值。
✳为新大象的位置
例1 2 3 4 ✳ 5 6 7 8 9
则ans的计算公式b3b4c4c5c6b7b8b9;
b3为max[1 2 3]; b4为max[2 3 4];
c4为max[3 4 ✳]; c5为max[4 ✳ 5]; c6为max[✳ 5 6];
b7为max[5 6 7]; b8为max[6 7 8]; b9为max[7 8 9];
由此可以归纳得到一个公式n个数每个窗口长度为m遍历到i时ans可以分成三段①[b(m)b(m1)...b(i-1)] ②[c(i-1)c(i)...c(im-2)] ③[b(im-1)...b(n)]
求max[]使用单调队列来求求ans用前缀和
anssumb[i-1]sumc[im-2]-sumc[i-2]sumb[n]-sumb[im-2]
但是还有ans某部分不存在的情况
当im时此时①不存在即anssumc[im-2]sumb[n]-sumb[im-2]
若in-m2时此时③不存在即anssumb[i-1]sumc[n]-sumc[i-2]
当imin-m2时anssumb[i-1]sumc[im-2]-sumc[i-2]sumb[n]-sumb[im-2]
代码 #include bits/stdc.h
using namespace std;
const int N 5e6 10;
int n, m, A, ans 0;
int a[N], b[N], c[N];
int sumc[N], sumb[N];
void getmax(int n, int m)
{dequeint q;for (int i 1; i n; i){if (!q.empty() q.front() i - m)q.pop_front();while (!q.empty() a[i] a[q.back()])q.pop_back();q.push_back(i);if (i m){b[i] a[q.front()];sumb[i] sumb[i - 1] b[i];}}
}
void getmax2(int n, int m)
{dequeint q;for (int i 1; i n; i){if (!q.empty() q.front() i - m)q.pop_front();while (!q.empty() a[i] a[q.back()])q.pop_back();q.push_back(i);if (i m){c[i] max(A, a[q.front()]);sumc[i] sumc[i - 1] c[i];}}
}int main()
{cin n m A;for (int i 1; i n; i){cin a[i];}getmax(n, m); // 求b[]getmax2(n, m - 1); // 求c[]for (int i 1; i n 1; i){if (i m){ans max(ans, sumc[i m - 2] sumb[n] - sumb[i m - 2]);}else if (i n - m 2){ans max(ans, sumb[i - 1] sumc[n] - sumc[i - 2]);}else{ans max(ans, sumb[i - 1] sumc[i m - 2] - sumc[i - 2] sumb[n] - sumb[i m - 2]);}}cout ans;return 0;
}
