[BaekJoon]2529不等式

17063 ワード
白駿 ついせき テキストリンク

🔦 提问链接


▼▼私の草

  • 브루트포스で解決した問題

  • 最大値と最大値を1つ必要とするだけで、時間を節約するために前後にループできます.

  • 汎用:0 ~ 9まで、数字を文字数より多く並べ替えます.

  • MIN値
  • シーケンスなので、小さい値から.
  • で求めたシーケンスから1つを選択し,不等式前後の値を比較する.
  • 条件が個数を満たす場合、その順序で最高値が更新される.
  • の最高値を求めたので、繰り返し文から逃げ出した.
  • MAX値
  • ソートリストの後からソートを開始します.
  • 不等式の前後の値を比較します.
  • の条件が正しい場合、この順序で最高価格が更新されます.
  • の最高値を得たので、重複文から逃げ出した.

    • 🛠 マイコード

    import itertools

num=input()
sign = input().split()
val=[str(x) for x in range(10)]
per = list(itertools.permutations(val, int(num)+1))
flag = 0
min_v = '9999999999'
max_v = '-1'
for comp in per:
    flag=0
    for i in range(int(num)):
        if sign[i]== '<' and comp[i] < comp[i + 1]:
            flag += 1
        elif sign[i]== '>' and comp[i] > comp[i + 1]:
            flag += 1
        else:
            break
    if flag == int(num):
        min_v = min(min_v, str(''.join(comp)))
        break


for k in range(len(per)-1,0,-1):
    flag=0
    for i in range(int(num)):

        if(sign[i]=='<' and per[k][i] < per[k][i+1]):
            flag += 1
        elif(sign[i]=='>' and per[k][i] > per[k][i+1]):
            flag += 1
        else:
            break
    if flag == int(num):
        max_v = max(max_v, str(''.join(per[k])))
        break
print(max_v)
print(min_v)

    ▼▼▼その他▼▼▼


  • より効率的です.

  • DFSが中間が不可能であると判断した場合,これらはすべて除外される.(場合によっては大幅に削減可能)
  • 0 ~ 9に繰り返し、이미 있는 값と부등호에 만족하는 값の認知を検査し、次のステップを行う.
  • idxが条件を満たす場合、最大、最小値が更新されます.

    • 🛠 その他のコード

    import sys

n = int(input())
oper = input().split()
check = [False] * 10
v = []
mn = sys.maxsize
mn_str = ""
mx = -1
mx_str = ""


def possible(i):
    if oper[i - 1] == '>' and v[i - 1] < v[i]:
        return False
    elif oper[i - 1] == '<' and v[i - 1] > v[i]:
        return False
    return True


def dfs(idx):
    global mn, mx, mn_str, mx_str
    if idx == n + 1:
        v_str = ''.join(map(str, v))
        val = int(v_str)
        if mn > val:
            mn = val
            mn_str = v_str
        elif mx < val:
            mx = val
            mx_str = v_str
        return
    else:
        for i in range(10):
            if check[i] is True:
                continue
            check[i] = True
            v.append(i)
            if idx == 0 or possible(idx):
                dfs(idx + 1)
            check[i] = False
            v.pop()


dfs(0)
print(mx_str)
print(mn_str)

    📝 整理する

  • では、すべての状況の数を測定する問題はほとんどありません.
  • で適用できる条件を考えてみましょう.

    • 🎈 リファレンス


    黄牛開発者ブログ
    [白俊]2225:合分解(Python)
    AVPlayer問題記録