1859号(百万長者計画)
13052 ワード
質問元:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=1859&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1は簡単な問題で、最初は想像以上に時間がかかりました. プライマリロジックは、現在の状態で最も値を検索し、その前に評価します.前の個数に最小値を乗じて、前の和を減算します. をアレイの要素の最後に繰り返します.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
private static long result;
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine()); // 테케 개수
for (int i = 0; i < T; i++) {
result = 0;
int N = Integer.parseInt(reader.readLine()); // 연속된 일수
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int[] days = new int[N];
for (int j = 0; j < N; j++) {
days[j] = Integer.parseInt(tokenizer.nextToken());
}
process(days, 0, N);
sb.append("#").append(i + 1).append(" ");
sb.append(result).append("\n");
}
System.out.println(sb);
}
// start 포함, end 미포함
private static void process(int[] days, int start, int end) {
if (start == end) return;
int max = Integer.MIN_VALUE;
int maxIndex = 0;
int sum = 0;
for (int i = start; i < end; i++) {
if (days[i] > max) {
max = days[i];
maxIndex = i;
}
}
for (int i = start; i < maxIndex; i++) {
sum += days[i];
}
result += days[maxIndex] * (maxIndex - start) - sum;
process(days, maxIndex + 1, end);
}
}
Reference
この問題について(1859号(百万長者計画)), 我々は、より多くの情報をここで見つけました https://velog.io/@ghc1124/SW-Expert-Academy-1859번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol