BOJ #17828

5621 ワード
greedy アルゴリズム#アルゴリズム# テキストリンク

LEVEL :
Gold5
質問の概要:
文字列を作成してXという整数を作成し、その整数を満たす辞書の順序で最も速い文字列を検索します.
ソリューション:
まず問題を見て最初に思いついたのは,時間的複雑度がO(N)以内であることである.
まず「A」=1とし,1に満ちた配列から配列の最後から調整を行う.Xという名前のターゲット整数から現在の配列の和を減算し、25より大きいか25以下かを計算し、for文を行い、X==配列の和が等しい瞬間をキャプチャします.
結果は問題を解決したが,他の回答者に比べて時間的複雑さの面ではそれほど優れたアルゴリズムではないようだ.
他の人はO(1)だけで解けた...ううう
原理は同じだ25で割ったシェアと剰余を用いてfor文字自体を変換することなく,その値を満たす整数値を直接求める.
それも当てはまって、今度は私もそう思うでしょう、ほほほ?
Solution

import sys
input = sys.stdin.readline

if __name__ == "__main__" :
    N , X = map(int, input().strip().split())
    arr = [1]*N
    sum_x = N
    for i in range(N) :
        if X-sum_x == 0 :
            break
        elif X-sum_x < 0 :
            arr = []
            break
        elif X-sum_x <= 25 :
            arr[N-1-i] += X-sum_x
            sum_x += X-sum_x
        elif X-sum_x > 25 :
            arr[N-1-i] += 25
            sum_x += 25
        if i == N-1 and  X > sum_x : 
            arr = []
            break
    if arr :
        string = []
        for num in arr :
            ch = chr(num+64)
            string.append(ch)
    print("".join(string) if arr else "!")
Javascript small pieces
PostgreSQLバックアップ暗号化方法