import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class SWEA1859 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack<Integer>();
for (int tc = 1; tc <= T; tc++) {
// 2 <= n <= 1,000,000
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
int[] price = new int[n];
for (int i = 0; i < n; i++) {
price[i] = Integer.parseInt(st.nextToken());
}
long ans = 0;
// 각각의 값들을 비교해주기 위해 우선 맨 오른쪽 집어넣고
stack.push(price[n - 1]);
// 오른쪽부터 stack에 넣어가면서
for (int i = n - 2; i >= 0; i--) {
int ith = price[i];
int top = stack.peek();
// 팔수 있는 경우가 갱신되는 경우
if (ith >= top) {
stack.pop();
stack.push(ith);
} else {
// top보다 작으면 사고 팔 수 있는 경우의 수
ans += top - ith;
}
}
sb.append(String.format("#%d %d%n", tc, ans));
stack.clear();
}
System.out.println(sb);
}
}
백준에서는 분명 골드 정도 되는 문제였던 것 같은데, 어떻게 이게 D2지...
'온라인 저지 > SWEA' 카테고리의 다른 글
[SWEA/Java] 5644 무선 충전 (0) | 2022.02.18 |
---|---|
[SWEA/Java] 1974 스도쿠 검증 (0) | 2022.02.18 |
[SWEA/Java] 4012 요리사 (0) | 2022.02.16 |
[SWEA/Java] 6808 규영이와 인영이의 카드게임 (0) | 2022.02.16 |
[SWEA/Java] 5432 쇠막대기 자르기 (0) | 2022.02.13 |
댓글