Written by @Yue_chen

题意：

给定一个长度为 n 的数组和一个 x。

数组会循环延长，数组前缀的第几位能超越x

思路：

开一个ans直接循环加数组会tle。

优化一下枚举方法：

求出一个循环数组的总和 sum，x/sum 得到会完整经过 cnt 次循环数组 。

now = cnt * sum，t = n * cnt

用处理好的次数再去再枚举加上一遍数组的每一位，直到大于x时结束。

时间复杂度O(n)

AC代码：

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

using i64 = long long;

void solve() {
    int n; cin>>n;
    
    i64 sum = 0;
    vector<int> a(n+1); 
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
        sum += a[i];
    }
    
    i64 x; cin>>x;
    
    i64 cnt = x / sum;
    i64 t = cnt * n;
    i64 now = cnt * sum;
    while(now <= x) {
        now += a[t%n+1];
        t++;
    }
    
    cout<<t<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

最优解唯一

1.预存递增和O(N)

2.计算前缀O(1)

3.二分查找尾巴O(logN)