【白俊】1806号部分プラス/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
26.ダブルポインタ
二重ポインタアルゴリズムとmeetin the middleアルゴリズムを学びましょう.
Java/Python
3.部分連結
1806号
片側から2つのポインタを移動する問題
これは、10000個以下の自然数からなる長さNの数列が与えられると、その数列における連続する数の部分和のうち、SまたはS以上の数の最短長さを求めるプログラムである.
部分和とは、開始点と終了点を指定することによって、その領域内の要素の和を求めることです.
この問題は必ずしも部分和を用いる必要はなく,二重ポインタとしてもよい.
Pythonは両方で解読した.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
long S = Long.parseLong(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
int result = 100001, sum = 0;
int point1 = 0, point2 = 0;
while(true){
if(sum >= S){
sum -= arr[point1++];
result = Math.min(result, (point2 - point1) + 1);
}
else if(point2 == N) break;
else sum += arr[point2++];
}
if(result == 100001) bw.write("0\n");
else bw.write(result + "\n");
bw.flush();
br.close();
bw.close();
}
}import sys
N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
start, end, temp = 0, 0, 0
result = 100001
while True:
if temp >= S:
result = min(result, end - start)
temp -= arr[start]
start += 1
elif end == N:
break
else:
temp += arr[end]
end += 1
if result == 100001:
result = 0
print(result)import sys
N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
prefix = [0]*(N+1)
start, end = 0, 1
for i in range(1, N+1):
prefix[i] = prefix[i-1] + arr[i-1]
result = 100001
while start < N:
if prefix[end] - prefix[start] >= S:
result = min(result, end - start)
start += 1
else:
if end < N:
end += 1
else:
start += 1
if result == 100001:
result = 0
print(result)Reference
この問題について(【白俊】1806号部分プラス/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-1806번-부분합-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol