单调栈题目

给定一个长度为 n 的序列 (s1, s2, · · · , sn) 和三个数 a, b, c 你需要找出一对L, R 满足如下式子:∑RiLsi a(bR − cL), 1 ≤ L ≤ R ≤ n即序列中的第 L 至 R 项之和大于 a · (b · R − c · L)求出满足条件的 L, R中 R − L 1 的最大值。输入格式输入的第一行包含四个整数 n, a, b, c 相邻整数之间使用一个空格分隔。第二行包含 n 个整数 s1, s2, · · · , sn 相邻整数之间使用一个空格分隔。输出格式输出一行包含一个整数表示答案。样例输入4 1 5 6 1 2 3 4样例输出3提示【评测用例规模与约定】对于 60% 的评测用例n ≤ 5000 对于所有评测用例1 ≤ n ≤ 3 × 1e5 1 ≤ a, b, c ≤ 1000 |si| ≤ 1e9#include iostream #include vector #include algorithm using namespace std; typedef long long ll; int main() { // 优化输入输出效率 ios::sync_with_stdio(false); cin.tie(NULL); int n; ll a, b, c; if (!(cin n a b c)) return 0; // 计算前缀和 P // 注意s[i] 最大 10^9n 最大 3*10^5前缀和需用 long long vectorll p(n 1, 0); for (int i 1; i n; i) { ll s_val; cin s_val; p[i] p[i - 1] s_val; } // A[i] p[i] - a * b * i // B[j] p[j] - a * c * (j 1) // 1. 构建单调递减栈存储 B 的下标 vectorint st; for (int j 0; j n; j) { ll val_B p[j] - a * c * (j 1); if (st.empty()) { st.push_back(j); } else { ll last_B p[st.back()] - a * c * (st.back() 1); // 只有当当前的 B 比栈顶更小时它才可能成为更优的左端点 if (val_B last_B) { st.push_back(j); } } } int max_len 0; // 2. 从右向左遍历右端点 i匹配左端点 j for (int i n; i 1; i--) { ll val_A p[i] - a * b * i; // 当 A[i] B[栈顶] 时尝试更新并弹出 while (!st.empty()) { int j st.back(); ll val_B p[j] - a * c * (j 1); if (val_A val_B) { // 确保满足 L R即 j1 i j i if (i j) { max_len max(max_len, i - j); } // 弹出 j因为当前的 i 是它能匹配的最右侧位置 st.pop_back(); } else { // 栈是递减的如果连栈顶都打不动由于 A[i] 不变里面的更打不动 break; } } } cout max_len endl; return 0; }