题解 - 序列

题目描述

小明和小花在研究重复序列了。
给定一个有N个正整数组成的序列a1,a2,…aN，然后我们可以把这个序列重复无限次，然后依次摆放，就变成了a1,a2,…aN,a1,a2,…aN,a1,a2,…aN,…，这些无穷的重复序列构成了一个新的序列b，即b1=a1,b2=a2,…,bN=aN,bN+1=a1,bN+2=a2,…,b2N=aN,…。
现在，小明希望求出满足下列条件的最小的k：

即使得b1+b2+…+bk> X的最小k值。

输入

输入第一行是一个正整数N，表示a序列的正整数个数。
输入第二行是有N个正整数组成，空格隔开。
输入第三行是一个正整数X。

输出

输出满足条件的最小的k值。

样例

样例输入

【输入样例1】
2
1 2
5
【输入样例2】
3
3 5 2
26
【输入样例3】
4
12 34 56 78
1000

样例输出

【输出样例1】
4
【输出样例2】
8
【输入样例3】
23

提示

分析

a数组不断复制得到b数组，求使得b1+b2+…+bk> X的最小k值

由于数组元素均为正数，故前缀和具有单调性，可以考虑二分

由于数组a不断复制，是一个不断重复的过程，即有周期性，故我们可以将每个完整的a数组看成一组，分别求出系数k和余数p，

最终结果即为 k * n + upper_bound(s,s + 1 + n,p) - s

注意数据范围，第8-10组数据ai可以达到1e18，直接求前缀和会爆LL，

注意到数据有特殊性质，即 ai和X均可以被1e12整除，预处理即可

时间复杂度 O(n)

代码

#pragma GCC optimize(2)
   
#include<bits/stdc++.h>
    
using namespace std;
    
typedef long long LL;
    
const int N = 1e5 + 10;
  
int n;
LL a[N],s[N];
string x;
  
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
  
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(a[i] > 1e9) a[i] /= 1e12;
        s[i] = s[i - 1] + a[i];
    }
    cin >> x;
    if(x > "1000000000000000000") x = x.substr(0,x.size() - 12);
    LL xx = stoll(x);
  
    LL k = xx / s[n],p = xx % s[n];
  
    cout << k * n + upper_bound(s,s + 1 + n,p) - s;
  
    return 0;
}