哈尔滨工业大学（威海）第九届ACM程序设计竞赛 Virtual Youtuber

佚名 6年前 (2019-04-16) 随笔 471人围观抢沙发百度已收录

链接

[https://ac.nowcoder.com/acm/contest/624/G]

题意

其实题意说的辣鸡死了，没有说明确。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

y is the subsequences that its sum is strictly less than p, regardless of the length.
y是什么这里就没有讲清楚，还让别人猜。浪费我生命
y就是子序列和不大于p的所有子序列长度之和。

分析

首先就是前缀和，
后面每次从第i个开始到最后一个找子序列之和等于或大于p的位置，就可以求出满足条件的这一段的长度。
用一个lower_bound().
然后就全部加起来

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
ll s[N];
int main(){
    int t,n; 
    ll x,p;
    scanf("%d",&t);
    for(int k=1;k<=t;k++){
        scanf("%d%lld",&n,&p);
         s[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            s[i]=s[i-1]+x;
        }
        ll cnt=0;
        for(int i=1;i<=n;i++)
        {
            int cur=lower_bound(s+i,s+n+1,s[i-1]+p)-s;
            cnt+=cur-i;
        }
        printf("Case #%d: %lld\n",k,cnt);
    }
    return 0;
}