本文共 1603 字，大约阅读时间需要 5 分钟。

给了n个数字，成一个环，最开始在第一个数字的位置上，每次移动就是向下移动一格。m次询问，每次询问给出一个x，求最少要移动多少次，使得经过的数值之和≥x。

思路

代码示例

#include 
   
    using namespace std;const int N = 3e5;typedef long long ll;ll sum[N], ma[N];int main() {    ma[0] = -2e9;    int T;    cin >> T;    while (T--) {        int n, m;        cin >> n >> m;        sum[0] = 0;        for (int i = 1; i <= n; ++i) {            int x;            cin >> x;            sum[i] = sum[i-1] + x;            ma[i] = max(ma[i-1], sum[i]);        }        while (m--) {            int x;            cin >> x;            if (ma[n] >= x) {                auto pos = lower_bound(ma+1, ma+n+1, x);                cout << (pos - ma) << " ";            } else {                if (sum[n] <= 0) {                    cout << "-1 ";                } else {                    ll cnt = (x - ma[n] - 1) / sum[n] + 1;                    int pos = lower_bound(ma+1, ma+n+1, cnt * sum[n] + ma[n] + 1) - ma;                    int res = cnt * n + pos - 1;                    cout << res << " ";                }            }        }    }    return 0;}
   

优化说明

该方法通过预处理前缀和和前缀最大值，结合二分查找和数学计算，高效地解决了每个查询问题，确保了算法的时间复杂度在可接受范围内。

转载地址：http://ybhwk.baihongyu.com/