Codeforces 1490G - Old Floppy Drive （二分、數學）

Codeforces Round #702 (Div. 3) G. Old Floppy Drive

題意

給定一個包含\(n\)個整數的數組\(\{a\}\)，可以循環延申至無窮個元素（定義編号\(n\)的後一個元素為編号\(1\)）

再給定\(m\)個詢問\(x\)，對于每個\(x\)

問無窮數組\(\{a\}\)的字首和數組\(\{S\}\)中，第一次出現\(S_i\ge x\)的下标\(i\)是多少（輸出時下标要\(-1\)）

若不存在，輸出\(-1\)

限制

\(1\le T\le 10^4\)

\(1\le n,m\le 2\cdot 10^5\)

\(-10^9\le a_i\le 10^9\)

\(1\le x_i\le 10^9\)

\(\sum n\le 2\cdot 10^5,\ \sum m\le 2\cdot 10^5\)

思路

注意求的是第一次出現\(a_i\ge x\)的下标\(i\)，不是\(a_i=x\)（讀錯題了，可惜）

記\(S_k=\sum_{i=1}^k a_i,\ M_k=\max_{i=1}^k S_i\)

根據\(\{M\}\)的定義

如果\(M_n\ge x\)，說明答案存在于\(1\)到\(n\)之間

又因為\(\{M\}\)是非遞減數組，是以可以通過二分查找來直接找到最小下标

否則，對\(S_n\)的正負性質進行讨論

• 如果\(S_n\le 0\)，又因為此時\(M_n\lt x\)，是以不存在任何一種狀态滿足\(S_i\ge x\)，故輸出\(-1\)
• 如果\(S_n\gt 0\)，

根據題意，\(S_{i+n}=S_i+S_n\)

定義\(d=x-M_n\)，表示詢問的值與\(1\)到\(n\)中所能得到最大的值的內插補點

于是發現，要想得到大于等于\(x\)的數，\(1\)到\(n\)中的最大值\(M_n\)還需要加上\(\lceil\frac d {S_n}\rceil\)遍\(S_n\)才行

據上述，得到\(M_n+\lceil\frac d {S_n}\rceil*S_n\ge x\)

即\(M_n\ge x-\lceil\frac d {S_n}\rceil*S_n\)

故讓\(x\)減去\(\lceil\frac d {S_n}\rceil*S_n\)後，便能通過二分查找來直接找到最小下标，最後将下标加上\(\lceil\frac d {S_n}\rceil*n\)即為答案

代碼

(202ms/2000ms)

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

ll mx[200050];

void solve()
{
    int n,m;
    cin>>n>>m;
    
    ll s=0;
    for(int i=1;i<=n;i++)
    {
        ll d;
        cin>>d;
        s+=d;
        mx[i]=max(mx[i-1],s);
    }
    
    while(m--)
    {
        ll q;
        cin>>q;
        if(mx[n]>=q)
            cout<<(lower_bound(mx+1,mx+1+n,q)-mx)-1<<' ';
        else
        {
            if(s<=0)
                cout<<"-1 ";
            else
            {
                ll d=q-mx[n];
                ll tim=(d+s-1)/s;
                q-=tim*s;
                cout<<(lower_bound(mx+1,mx+1+n,q)-mx+tim*n)-1<<' ';
            }
        }
    }
    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;while(T--)
        solve();
    return 0;
}
           

https://blog.csdn.net/qq_36394234/article/details/113830619