题解：CF1899B 250 Thousand Tons of TNT

lailai0916 · 2023-11-19 13:52:04 · 题解

解题思路

显然 n 必须是 k 的倍数才能使每辆车的箱子数量相同，所以 n 的因子就是所有可能的 k。

枚举 n 的所有因子，对于每个因子 k，用前缀和计算 \frac{n}{k} 辆车重量的极差，最后取最大值即为答案。

时间复杂度为 O(\sum_{d|n}\frac{n}{d})=O(n\log\log n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=150005;
ll a[N];
ll f(int n,int k)
{
    ll mx=-inf,mn=inf;
    for(int i=0;i<n/k;i++)
    {
        ll val=a[k*(i+1)]-a[k*i];
        mx=max(mx,val);
        mn=min(mn,val);
    }
    return mx-mn;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        ll ans=-inf;
        for(int i=1;i<=n;i++)
        {
            if(n%i==0)ans=max(ans,f(n,i));
        }
        cout<<ans<<'\n';
    }
    return 0;
}