根据题意我们知道,不能选两个有交集的区间,我们只需要先选一遍最大的长度为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; }
全部评论
(2) 回帖