求大佬看看我的思路哪里不对

根据题意我们知道,不能选两个有交集的区间,我们只需要先选一遍最大的长度为k的区间,然后再遍历一遍选择大小为第二大的区间。

选择第二大的区间我的方案是不与上一个选出来的产生交集

// Problem: 数学考试
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/15553
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// Code by: ING__
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int T;
int n;
int k;
ll s[200010];

int main(){
    cin >> T;
    while(T--){
        cin >> n >> k;

        memset(s, 0, sizeof(s));

        for(int i = 1; i <= n; i++){
            ll x;
            cin >> x;
            s[i] = s[i - 1] + x;
        }

        // int ans = 0;

        // 选取第一大的区间

        ll maxa = -1e19;
        int r1;

        for(int i = k; i <= n; i++){
             if(maxa < s[i] - s[i - k]){
                 maxa = s[i] - s[i - k];
                 r1 = i;
             }
        }

        // 选取第二大的区间

        ll maxb = -1e19;

        for(int i = k; i <= n; i++){
            if(i >= r1 - k + 1 && i - k + 1 <= r1) continue;
            if(maxb < s[i] - s[i - k]){
                maxb = s[i] - s[i - k];
            }
        }

        cout << maxa + maxb << endl;
    }
    re 0;
}
全部评论
有问题,贪心是错的。先选一个最大值不能保证两个的和是最大值
点赞 回复 分享
发布于 2021-07-22 17:12
点赞 回复 分享
发布于 2021-07-21 19:20

相关推荐

练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务