洛谷P1714 切蛋糕 单调队列做法

2023-12-19 06:26:27

原题链接

https://www.luogu.com.cn/problem/P1714


题面

题目描述

今天是小 Z 的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了 n n n 个相同的小块,每小块都有对应的幸运值。

小 Z 作为寿星,自然希望吃到的蛋糕的幸运值总和最大,但小 Z 最多又只能吃 m ( m ≤ n ) m(m\le n) m(mn) 小块的蛋糕。

请你帮他从这 n n n 小块中找出连续 k ( 1 ≤ k ≤ m ) k(1 \le k\le m) k(1km) 块蛋糕,使得其上的总幸运值最大。

形式化地,在数列 { p n } \{p_n\} {pn?} 中,找出一个子段 [ l , r ] ( r ? l + 1 ≤ m ) [l,r](r-l+1\le m) [l,r](r?l+1m),最大化 ∑ i = l r p i \sum\limits_{i=l}^rp_i i=lr?pi?

输入格式

第一行两个整数 n , m n,m n,m。分别代表共有 n n n 小块蛋糕,小 Z 最多只能吃 m m m 小块。

第二行 n n n 个整数,第 i i i 个整数 p i p_i pi? 代表第 i i i 小块蛋糕的幸运值。

输出格式

仅一行一个整数,即小 Z 能够得到的最大幸运值。

样例 #1

样例输入 #1

5 2 1 2 3 4 5

样例输出 #1

9

样例 #2

样例输入 #2

6 3 1 -2 3 -4 5 -6

样例输出 #2

5

提示

数据规模与约定
  • 对于 20 % 20\% 20% 的数据,有 1 ≤ n ≤ 100 1\le n\le100 1n100
  • 对于 100 % 100\% 100% 的数据,有 1 ≤ n ≤ 5 × 1 0 5 1\le n\le5\times 10^5 1n5×105 ∣ p i ∣ ≤ 500 |p_i|≤500 pi?500

保证答案的绝对值在 [ 0 , 2 31 ? 1 ] [0,2^{31}-1] [0,231?1] 之内。


解题思路

求连续区间和,我们很容易想到前缀和,我们先预处理出前缀和数组s(s[i]=s[1]+s[2]+s[3]+……s[i-1]+s[i]),
然后我们首先有个非常朴素的想法是:对于以第i个元素结尾的子段,最大的子段和P(i)可以表示为P[i] = max{sum[i] - sum[j],i - m <= j <= i - 1},
于是有ans = max[P[i]],用O(n^2)的朴素算法枚举算出每个窗口区间的和然后找最大,
即:

for (int i = 1; i <= n; i++) {
   cin >> s[i];
   s[i] = s[i - 1] + s[i];
}
// 暴力解法,求出前缀和之后,用O(n^2)的朴素算法算出每个窗口区间的和,会超时
ll ans = -INF;
for (int i = 1; i <= n; i++) {
   for (int j = i - m + 1; j <= i; j++) {
       ans = max(ans, s[i] - s[j - 1]);    // [j, i]的区间和
   }
}
cout << ans << endl;

结合题目数据,这显然会超时。
我们考虑在这个朴素解法的基础上进行优化,将上面P[i]的计算式改写为
P[i] = sum[i] - min{sum[j], i - m <= k <= i - 1},
于是我们就要想方设法在优于O(M)的时间内实现获取最小的sum[j]。这个sum[j]必须是[i - m, i - 1]区间内最小的。
考虑设计这样一个数据结构,在更低的时间复杂度内获取最优Sum[j]。
可以想到单调队列。


代码(CPP)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
ll s[maxn], n, m;
deque<ll> q;

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = s[i - 1] + s[i];
    }
    // 暴力解法,求出前缀和之后,用O(n^2)的朴素算法算出每个窗口区间的和,会超时
    // ll ans = -INF;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = i - m + 1; j <= i; j++) {
    //         ans = max(ans, s[i] - s[j - 1]);    // [j, i]的区间和
    //     }
    // }
    // cout << ans << endl;

    /*
        我们考虑在这个朴素解法的基础上进行优化,将上面P[i]的计算式改写为
        P[i] = sum[i] - min{sum[j],  i - m <= k <= i - 1},
        于是我们就要想方设法在优于O(M)的时间内实现获取最小的sum[j]。这个sum[j]必须是[i - m, i - 1]区间内最小的。
        考虑设计这样一个数据结构,在更低的时间复杂度内获取最优Sum[j]。
        可以想到单调队列。
    */
    ll ans = -INF;
    q.push_back(0);     // 这里一定要特别注意,不加这个是会有空队列访问溢出的情况的
    for (int i = 1; i <= n; i++) {
        // 去尾:如果队尾的数字比当前数字大,则出队。保证队列从队头到队尾是递增的。
        while (!q.empty() && s[q.back()] > s[i]) {
            q.pop_back();
        }
        // 入队
        q.push_back(i);
        // 删头:如果队首的数字已经落在了窗口之外,则将其出队.保证窗口大小不超过m。
        while (!q.empty() && q.front() < i - m) {   
            q.pop_front();
        }
        ans = max(ans, s[i] - s[q.front()]);
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}

文章来源:https://blog.csdn.net/qq_45554473/article/details/135074032
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。