题目
题目描述:今天qwb要参加一个数学考试,这套试卷一共有n道题,每道题qwb能获得的分数为ai,qwb并不打算把这些题全做完,
他想选总共2k道题来做,并且期望他能获得的分数尽可能的大,他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1],[R,R+1,R+2,...,R+k-1](R >= L+k)。
第一行一个整数T(T<=10),代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an,(-100,000<=ai<=100,000)
输出一个整数,qwb能获得的最大分数
解析
这道题说要求区间和,我们自然而然就能想到前缀和。
这道题我一开始想到先求最大区间,再在两边求次大区间,但是硬核66.7%(其实我知道是错的,但是不知道原因)
for (int i = 0, j = k; j <= n; i++, j++) if (ans1 < sum[j] - sum[i]) { ans1 = sum[j] - sum[i]; l = i, r = j; } int ans2 = -INF; for (int i = 0, j = k; j <= l; i++, j++) ans2 = max(ans2, sum[j] - sum[i]); for (int i = r, j = r + k; j <= n; i++, j++) ans2 = max(ans2, sum[j] - sum[i]); printf("%d\n", ans1 + ans2);
所以呢,在前缀和的基础上,我们还是要求两个区间。
算法讲解:
- 首先,这道题,我们的区间是定长的,为k。
- 然后我们要求两个区间:所以区间肯定!一个左一个右。(废话)
- 但是我们这样就能想到,我们确定一个点,然后对左右区间求极值不就好了?
ll lans = -INF, rans = -INF; for (int i = k; i + k <= n; i++) { lans = max(lans, sum[i] - sum[i - k]); rans = max(rans, sum[i + k] - sum[i]); }
- 但是这样肯定是不对的!因为左右区间可能重合。那怎么样才是对的呢?
- 我们既然这样有可能重合,所以我们就要让他不能重合,所以只求左边的极值。右边就在左边的基础上求极值就行了。
ll lans = -INF, ans = -INF; for (int i = k; i + k <= n; i++) { lans = max(lans, sum[i] - sum[i - k]); ans = max(ans, lans + sum[i + k] - sum[i]); }
比如这样~
打代码:
- 存数据
- 找区间
- 出答案
- 484很有道理!看代码吧~
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; //代码预处理区 const ll INF = 0x3f3f3f3f3f3f3f3f; const int MAX = 2e6 + 7; ll sum[MAX]; //全局变量区 template<class T>inline void read(T& res); //函数预定义区 int main() { int T; read(T); while (T--) { int n, k; read(n); read(k); sum[0] = 0; for (int i = 1; i <= n; i++) { read(sum[i]); sum[i] += sum[i - 1]; } ll lans = -INF, ans = -INF; for (int i = k; i + k <= n; i++) { lans = max(lans, sum[i] - sum[i - k]); ans = max(ans, lans + sum[i + k] - sum[i]); } printf("%lld\n", ans); } return 0; } template<class T>inline void read(T& res) { char c; T flag = 1; while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = -1; res = c - '0'; while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0'; res *= flag; } //函数区