文章

68

粉丝

691

获赞

26

访问

578.4k

头像
尺取法
P1570
发布于2020年5月29日 13:04
阅读数 7.4k

 

#define vec vector<int>
#define inf 0x3f3f3f3f
#define MAX 100005
#define P pair<int,int>
#define MOD 1000000

int main() {
	int T, n, m, a[MAX], sum[MAX]; cin >> T;
	while (T--) {
		cin >> n >> m; sum[0] = 0;
		for (int i = 1; i <= n; i++)cin >> a[i], sum[i] = sum[i - 1] + a[i];
		int l = 0, r = 1, cnt = inf;
		while (l <= n && r <= n) {//右端点超过n,说明sum[n]-sum[l]已经不可能大于m
			if (sum[r] - sum[l] >= m)//大于等于就更新右端点
				cnt = min(cnt, r - l), l++;
			else r++;//小于就更新左端点
		}
		cout << cnt << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发