题解：CF1733A Consecutive Sum

Talk_Lemon · 2024-07-16 11:44:58 · 题解

大致题意

给定一个长度为 n 的数组 a ，你可以进行最多 k 次下面的操作。

选择两个下标 i 和 j , 满足 i \bmod k = j \bmod k ( 1 \le i < j \le n ).

交换 a_i 和 a_j .

在进行完你的操作之后（不必用完 k 次操作的机会，你需要在数组中选择一段长度为 k 的区间，此区间的各个元素的和即为你的分数，请求出你能得到的最大分数。

思路

一眼贪心好题。可以看出当下标膜 k 同余时，就可以交换，简单证明后可得出，我们一定可以把膜 k 同余的最大数放到长度为 k 的区间里，简单模拟即可。

#include <bits/stdc++.h>
using namespace std;
long long a[105],b[105];
int main(){
    int t;
    cin>>t;
    while(t--) 
    {
        int n,k;
        cin>>n>>k;
        memset(a,0,sizeof a);//初始化 
        for(int i=1;i<=n;i++) 
        {
            cin>>b[i];
            a[i%k]=max(a[i%k],b[i]);
        }
        long long ans=0;//保险起见开 long long 
        for(int i=0;i<k;i++) 
            ans+=a[i];
        cout<<ans<<endl;
    }
    return 0;//完结散花
}