题目描述
//太过分了,太过分了,最后一个数据int越界了导致结果错误,还以为是代码错了改了半天,最后把所有数都该成了long就过了,真的是生气,也不给说一下数据类型
记录一下这题的思路,
首先通过分析题意可以知我们的目的是寻找一个区间k中的下标为0的值最大即可
所以只计算其中的下标为0的数据进行前缀和的计算就好了,把下标为1的数据忽略掉就可以了
注意:计算前缀和求区间和的时候最好下标从1开始,方便最终最终的计算
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
include[HTML_REMOVED]
using namespace std;
const int N = 1e5 +10;
int main(){
long n,k,d[N],s[N],dp[N];
long maxM =-1,left,right,sum = 0;
long res = 0;
cin>>n>>k;
for(int i = 1;i<=n;i) {//输入一个数组
cin>>d[i];
}
for(int i = 1;i<=n;i) cin>>s[i];//对应数组中每一个数的状态
for(int i =1;i<=n;i){//将不会变的下标为1的值相加上
if(s[i] == 1){
res += d[i];
}
}
for(int i =1;i<=n;i){//初始化前缀和数组,只前缀s[]中下标为0的元素
if(s[i] == 1)//当其下标为1时,将其忽略
dp[i] = dp[i-1];
else//当其下标为0时将其加入到前缀和中
dp[i] = dp[i-1] + d[i];
}
for(int i = 1;i<=n;i++){//i作为左边界,寻找一个最大的右边界使得在这个范围里得到的下标为0的数的和最大
int r = i+k-1;
if(r<=n){
sum = dp[r] - dp[i-1];//计算当前区间中的所有下标为0的数的和
if(sum>maxM){ //如果为0的和更大了,就更新一下left的值,和最大的值
left = i;
maxM = sum;
}
}
}
cout<<res + maxM; //最终结果就等于在区间k中0转1最大的那些值加上原来的数据
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH