题解：CF2086B Large Array and Segments

· · 题解

\mathbf{0x00} 启

蒟蒻的第 \color{red}\mathbf{58} 篇题解。

\mathbf{0x01} 承

将一个数组 a 复制 k 次形成数组 b，求出满足l 及其之后所有数的和大于等于 x 的 l 的数量。

\mathbf{0x02} 转

很显然，如果从后往前依次遍历 b 中的所有数并累加在 \text{sum} 中，如果在一个位置 sum\geq x 则在它之前的所有位置都满足条件。

记 a 数组中所有元素之和为 s，则在 b 数组中，有 \left\lfloor \frac{x}{s} \right\rfloor\times n 个数是一定不满足条件的（如果 x 是 s 的倍数则变为 (\left\lfloor \frac{x}{s} \right\rfloor-1)\times n）。然后单独处理一个数组中的数（这里其实是分块的思想，只不过没有起到优化的作用），记其中满足条件的有 c 个，那么答案就是 (k-p-1)\times n+c。

个人认为代码中的边界情况还是很不好处理的。

\mathbf{0x03} 合

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,k,x;
int main(){
    cin.tie(0),cout.tie(0)->sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>k>>x;
        vector<ll>a(n+1),g(n+1);
        ll sum=0,c=0;
        for(ll i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        if(sum*k<x){
            cout<<0<<endl;
            continue;
        }
        ll p=x/sum,q=x%sum,l=0;
        if(q==0)p--,q=sum;
        for(ll i=n;i>=1;i--){
            l+=a[i];
            if(l>=q){
                c=i;
                break;
            }
        }
        cout<<n*k-p*n+c-n<<endl;
    }
}