基本思路

• 基于逆向思维，由于题意我们只要求 [l,r]>=x 中 l 的个数，所以如果 l 可选。 则 $[l,n\timesk]>=x$ 必然成立。
• 因此我们转换一下，则对于所有满足 $S[l,n\timesk]<x$ 的集合中 l 的个数即为我们求解问题的反集 P 因此 $ans = |~P|$。
• 换个角度，我们完全可以翻转数组从 n ~ 1。
• 因此 [p,nk] => [1,r] 表示从第 nk 个元素加到倒数第 r 个元素的集合。
• 定义 S'[x] 表示从 nk 累加到倒数第 x 个元素之和。
• 所以我们有二分公式 $ans[r] = r/n*S'[n]+S'[r%n]<x$。
• 注意：如果使用前缀和查询 $O1$ 复杂度 $logn$ ，如果不计算前缀和就是 $nlogn$。

  题解

  #include <bits/stdc++.h>
  using namespace std;
  //const int N = 200005;
  #define int long long
  void solve();
  signed main()
  {
    //n <= 3/4 x
    //x >= 4n/3
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
  }
  const int N = 2e5+10;
  int num[N];
  void solve()
  {
    int n,k,x;
    cin>>n>>k>>x;
    for(int i = 1;i<=n;i++) cin>>num[i];
    reverse(num+1,num+1+n);
    for(int i = 1;i<=n;i++) num[i]+=num[i-1];
    int l = 1,r = n*k;
    while(l<=r)
    {
        int mid = l+r+1>>1;
        
        int ans = mid / n * num[n] + num[ mid % n ];//求<x 的右边界
        if(ans >= x)
        {
            r = mid-1;
        }
        else //小了就往左找
        {
            l = mid+1;
        }
    }
    int ans = 0;
    for(int i = l+10;i>=l-10;i--)//找到第一个小于的值
    {
        int r = i / n * num[n] + num[i % n];
        if(r<x)
        {
            ans = i;
            break;
        }
    }
    if(ans>n*k) cout<<0<<endl;
    else cout<<n*k-ans<<endl;
  }