Virtual Youtuber

The input contains multiple test cases.

The first line is an integer T(1 <= T <= 20), which indicates the number of test cases. Then T test cases follow.

The first line of each test cases contains two integers n, p(1 <= n <= 1e5, 1 <= p <= 1e18), represents the number of the live data sequence and the popular standard.

The second line contains n integers, represents the live data sequence L1...Ln, Li means that how many watchers were watching his stream in the time point i, 1 <= Li <= 1e12.

C++14(g++5.4) 解法, 执行用时: 443ms, 内存消耗: 2024K, 提交时间: 2019-04-14 12:48:22

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
ll pre[N],a[N];
int n;
ll p;
int main(void){
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d%lld",&n,&p);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            pre[i]=pre[i-1]+a[i];
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            int k=lower_bound(pre+1,pre+1+n,pre[i-1]+p)-pre-1;
            ans+=(1ll*(k-i+1));
            //printf("%d\n",k);
        }
        printf("Case #%d: %lld\n",cas,ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 491ms, 内存消耗: 3448K, 提交时间: 2019-04-16 14:21:10

#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;
}

详情