给点思路呗～

常规
1

3. 小埋过生日

题目ID：15847必做题100分

最新提交：

Wrong Answer

0 分

历史最高：

Wrong Answer

0 分

时间限制: 1000ms

空间限制: 65536kB

题目描述

题目描述

小埋马上就要过生日了，小埋的朋友们合伙送了 一块蛋糕，这块蛋糕是一个长方体，被不同色彩分成了𝑛n个相同的小块，每小块都有对应的幸运值。

小埋作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但是小埋的肚子容量是有限的，最多只能吃𝑚(𝑚<=𝑛)m(m<=n)小块的蛋糕。

小埋请你帮他从这n小块蛋糕中找出连续的𝑘(1<=𝑘<=𝑚)k(1<=k<=m)块蛋糕，使得其上的总幸运值最大。

输入格式

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

第二行有𝑛n个整数，第i个整数𝑝𝑖pi​代表第i小块蛋糕的幸运值。

输出格式。

输出一行仅一个整数，即小埋能够得到的最大的幸运值。

样例 #1

样例输入 #1

5 2
1 2 3 4 5

样例输出 #1

9

样例 #2

样例输入 #2

6 3
1 -2 3 -4 5 -6

样例输出 #2

5

提示

1<=𝑚<=𝑛<=5∗10^5

∣𝑝_𝑖|<=500∣

保证答案的绝对值在整数范围内。

2 个赞
2

？？？这是提高组的吗？

2 个赞
3

普及组的

2 个赞
4

我用的是前缀和的暴力，可以拿50分

1 个赞
5 
#include<bits/stdc++.h>
#define M 1000005
using namespace std;
int res[M], a[M], n, k, cnt;
signed main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++) 
        //输入并计算前缀和;
    for(int i = 1;i <= n - k + 1;i++) 
        for(int j = 1;j <= k;j++) 
            //枚举所有情况并计算答案（最大值）
    for(int i = n - k + 2;i <= n;i++) 
        cnt = max(cnt, res[n] - res[i - 1]);//这是后面k-1个元素的组合
    //输出答案
    return 0;
}
1 个赞
6

应该是先求前缀和，然后一个一个进，弄一个单调递增队列,队头和队尾的差最大就是所需的答案

2 个赞
7

单调递增队列是什么？ @连晨皓
就是优先队列吗？

1 个赞
8

类似于优先队列，但只是类似

1 个赞
9

什么意思？

1 个赞
10

@连晨皓 一点都不类似！

1 个赞
11

不是那是啥？
长什么样？

1 个赞
12

@冯俊骁 明明是一模一样！

1 个赞
13

那怎么访问队尾？

1 个赞
14

@冯俊骁 你要访问什么的队尾？

1 个赞
15

image
样例怎么操作？

1 个赞
16

@冯俊骁 我都看不见题目（你另外发一个帖子

1 个赞
17

问 deep seek 好了

1 个赞
18

（帖子已被作者删除）

1 个赞
19

@连晨皓 难道单调递增能访问队尾吗？

1 个赞
20

当我没说

1 个赞