Tổng liên tiếp không quá t
Xem PDF
Điểm:
1500
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một mảng gồm \(n\) số nguyên và số nguyên \(t\).
Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá \(t\). Và số lượng phần tử của mảng này chính là kết quả cần tìm.
Input
-
Dòng thứ nhất chứa hai số nguyên \(n,t(1\le n\le 10^5;1\le t\le 10^9)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^4)\)
Output
- In ra giá trị cần tìm.
Example
Test 1
Input
4 4
1 2 1 2Output
3Note
Giải thích: Mảng con gồm những phần tử \(a_1,a_2,a_3\) là mảng con có độ dài lớn nhất ta cần tìm vì chúng thoả mãn yêu cầu bài toán.
Bình luận
include<bits/stdc++.h>
using namespace std;
const int sm=1e6+3;
int n,a[sm],t=0,s,m=0;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>s; for(int i=0; i<n; i++) cin>>a[i];
int l=0, r=0;
while(r<n) { t+=a[r]; while(t>s) {t-=a[l]; l++;}
m=max(m,r-l+1);
r++;
}
cout<<m;
return 0;}
n,t = map(int,input().split())
a = list(map(int,input().split()))
s = 0
j = 0
MAX = 0
for i in range(n):
s += a[i]
if (s>t):
while (s>t):
s -= a[j]
j += 1
else:
MAX = max(MAX,i-j+1)
print(MAX)
jumptozero anh cho em xin link bài này bên Codeforces ạ
tui tin pref+chặt sẽ ac
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
ai giúp em với ạ bài này quy hoạch động thế nào ạ
dùng deque cũng ac được, đỡ phải xa xôi gì:>
Uồi bài này dùng Queue cũng khá ảo :v
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.