【滑动窗口】ABC267 C - Index × A(Continuous ver.)

Dear 丶 2024-03-23 10:04 50阅读 0赞

**虽然这是一个简单题，但是感觉好帅，想记录一下**

[C - Index × A(Continuous ver.) (atcoder.jp)][C - Index _ A_Continuous ver._ _atcoder.jp]

题意：

![950e5f2a1b654caca5a08a4b0de0510e.png][]

![86d5e8ae75f74ceb915018db8eb24656.png][]

思路：  
**考虑往DS方向想：先考虑我们需要维护什么，然后再去考虑修改操作对需要维护的东西的影响，再去更新需要维护的东西**

答案要求的是一个区间内1\*ai+2\*a(i+1)+....，所以我们考虑暴力维护这个区间的这个值

然后去考虑修改：往右移动一格窗口，贡献的变化如下：

![ef7b40875d9f40b48f40432e2a751b11.jpeg][]

所以我们需要维护变化的这个部分

其中波浪线部分直接可以维护区间和，然后左边少的那个和右边多的那个直接在移动窗口的时候维护就行

虽然是简单题，但是这就是DS的含金量！

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    int n,m;
    int a[mxn];
    void solve(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int in=0,sum=0;
    	int ans=-1e18;
    	for(int i=1;i<=m;i++){
    		in+=a[i];
    		sum+=i*a[i];
    	}
    	ans=max(ans,sum);
    	for(int i=m+1;i<=n;i++){
    		sum-=in;
    		in-=a[i-m+1-1];
    		in+=a[i];
    		sum+=a[i]*m;
    		ans=max(ans,sum);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[C - Index _ A_Continuous ver._ _atcoder.jp]: https://atcoder.jp/contests/abc267/tasks/abc267_c
[950e5f2a1b654caca5a08a4b0de0510e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/cd9524333a2b498fa8701468191b02ba.png
[86d5e8ae75f74ceb915018db8eb24656.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/cefd0d8ee89e41f29e6cfe5f6a843523.png
[ef7b40875d9f40b48f40432e2a751b11.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/aca7fa14edfe40d2821ddd2dcabcd60b.png