G. Old Floppy Drive 二分

G. Old Floppy Drive

题目大意：

给你一个 \(a\) 序列，大小为n，给你一个询问序列 \(x\) ，大小为 \(m\) ，问：对于第 \(i\) 个询问， \(x_i\) ，从 \(a\) 序列的第一个元素开始，把经过的元素相加，问经过最少多少步，和至少为 \(x_i\) ，因为 \(a\) 是放在一个圆盘上，所以 \(a\) 序列的最后一个元素的下一个元素是第一个元素。

题解：

• 首先可以求一个前缀和
• 然后把一个递增的序列存下来
• 之后对于每一个询问，首先判断是不是这个递增序列的最大值，如果比这个最大值还要大，那么就判断 整个 \(a\) 序列的和是不是一个大于0的数，是的话，则可以求整个a序列经过的次数，然后再加上一个值。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
ll a[maxn],x[maxn],sum[maxn];
struct node{
    ll id,sum;
    node(ll id=0,ll sum=0):id(id),sum(sum){}
}e[maxn];
int now;
ll ok(ll x){
    int l = 1,r = now,ans = 0;
    while(l<=r){
        int mid = (l+r)>>1;
        if(e[mid].sum>=x) ans = e[mid].id,r = mid - 1;
        else l = mid + 1;
    }
    return ans - 1;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        now = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
            if (sum[i] > e[now].sum) e[++now] = node(i, sum[i]);
        }
        ll maxs = now > 0 ? e[now].sum : -1, S = sum[n];
        for (int i = 1; i <= m; i++) {
            scanf("%lld", &x[i]);
            if (maxs >= x[i]) {
                int ans = ok(x[i]);
                printf("%d", ans);
            } else {
                if (S <= 0) printf("-1");
                else {
                    ll num = (x[i] - maxs + S - 1) / S;
                    ll res = x[i] - num * S;
                    ll ans = num * n + ok(res);
                    printf("%lld", ans);
                }
            }
            if(i==m) printf("\n");
            else printf(" ");
        }

    }
}

G. Old Floppy Drive 二分

原文：https://www.cnblogs.com/EchoZQN/p/14529225.html