https://www.acmicpc.net/problem/1806
1806호: 소계
첫 번째 줄은 N(10 ≤ N < 100,000) 및 S(0 < S ≤ 100,000,000)를 지정합니다.
두 번째 줄에는 시퀀스가 포함되어 있습니다.
시퀀스의 각 요소는 공백으로 구분되며 10,000 미만의 자연수입니다.
'추천 관련글,
www.acmicpc.net
2개의 포인터를 이용하여 원하는 값을 추출하는 2개의 포인터 알고리즘 문제입니다.
연속된 수의 소계 중에서 수열의 최소 길이는 합이 S보다 크거나 같은 수열에서 찾습니다.
테스트 케이스를 예로 설명하겠습니다.
10 15
5 1 3 5 10 7 4 9 2 8start 및 end 변수를 설정하고 조작하여 원하는 최소 시퀀스 길이를 얻어야 합니다.
합계(소계) < S(명목값)이면 최종값을 증가
sum(subtotal) >= S(nominal value)인 경우, 시작값을 증가시키고 시퀀스의 최소 길이를 업데이트합니다.
이 논리에 따라 5와 10이 시퀀스의 최소 길이가 됩니다.
#include <iostream>
#include <vector>
int a(100001);
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a(i);
}
int i = 0, j = 0, sum = a(0), ans = 210000000;
while (j < n)
{
if (sum < m)
{
j += 1;
sum += a(j);
}
else if (sum == m)
{
if (j - i + 1 < ans)
{
ans = j - i + 1;
}
j+=1;
sum += a(j);
}
else if (sum > m)
{
if (j - i + 1 < ans)
{
ans = j - i + 1;
}
sum -= a(i);
i++;
}
}
if(ans > n) ans = 0;
cout<<ans;
}