双指针 WA #15 #28 求帮忙QAQ
查看原帖
双指针 WA #15 #28 求帮忙QAQ
542905
WannaYellow楼主2022/11/14 17:02
#include<bits/stdc++.h>

using i8=char;		using u8=unsigned char;
using i16=short;	using u16=unsigned short;
using i32=int;		using u32=unsigned int;
using i64=long long;using u64=unsigned long long;
using i128=__int128;using u128=unsigned __int128;
using f32=float; 	using f64=double;				using f128=long double;

template<typename T> inline void read(T &x){
	char ch=getchar(),f=0;
	x=0;
	while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')(x=x*10+(ch-'0')),ch=getchar();
	x=(f?-x:x);
}
template<typename T,typename ...Ts> void read(T &x,Ts &...xs){read(x); read(xs...); }
char fostk[50]; u8 cntfostk;
template<typename T> inline void write(T x){
	if(x<0)putchar('-'),x=-x;
	while(x>9)fostk[++cntfostk]='0'+x%10,x/=10;
	fostk[++cntfostk]=x+'0';
	while(cntfostk)putchar(fostk[cntfostk--]);
}
template<typename T> void writesp(T x){write(x); putchar(' '); }
template<typename T> void writeln(T x){write(x); putchar('\n'); }
template<typename T> void writelns(T x){writeln(x); }
template<typename T,typename ...Ts> void write(T x,Ts ...xs){writesp(x); write(xs...); }
template<typename T,typename ...Ts> void writeln(T x,Ts ...xs){write(x,xs...); putchar('\n'); }
template<typename T,typename ...Ts> void writelns(T x,Ts ...xs){writeln(x); writelns(xs...); }
i32 n,K;
u64 sum[1000006];
std::queue<i32> ans;
i32 main(){
#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	freopen("test.err","w",stderr);
#endif
	read(n);
	for(i32 i=1;i<=n;i++){
		read(sum[i]);
		sum[i]+=sum[i-1];
	}
	read(K);
	i32 l=0,r=1; 
	for(i32 i=1;i<=K;i++){
		while(sum[r+1]-sum[l]<=i&&r<n)r++;
		while(sum[l+1]<=i&&sum[l]<sum[r]-sum[l]&&l<n)l++;
		while(sum[r+1]-sum[l]<=i&&r<n)r++;
		if(sum[l]>sum[r]-sum[l])ans.push(i);
	}
	// writeln(l,r);
	writeln(ans.size());
	while(!ans.empty())writesp(ans.front()),ans.pop();
	return 0;
}
2022/11/14 17:02
加载中...