[BOJ]分配11941ハンバーグ(Python)

17303 ワード
白駿 テキストリンク
テーブルの上にハンバーガーと人が置いてあり、一定距離しか食べられないハンバーガーの場合、問題はハンバーガーが食べられる人の数を見つけることです.グリディアルゴリズムのビデオを見て、関連問題を解いた.
サンプル入力と任意入力の値が正しい値に出力され、コミット後にタイムアウトが発生します.

タイムアウトコード

import sys
N,K=map(int,sys.stdin.readline().split())
cnt=0
change=[0 for x in range(N)]
perli=list(map(str,sys.stdin.readline().strip()))
for i in range(len(perli)):
    if perli[i]=='P':
        if i-K>=0:
            perli[0:i-K]=change[0:i-K]
            perli[i]=0
            newli=perli[i-K:i+K+1]
            for x in range(len(newli)):
                if newli[x]=='H':
                    newli[x]=0
                    cnt+=1
                    perli[i-K:i+K+1]=newli
                    break
        else:
            perli[i]=0
            newli2=perli[:i+K+1]
            for y in range(len(newli2)):
                if newli2[y]=='H':
                    newli2[y]=0
                    cnt+=1
                    perli[:i+K+1]=newli2
                    break   
print(cnt)
これはmin,max関数を用いて簡単に解くことができる提案に基づいて作成されたコードである.上のコードよりずっと簡単です.

リファレンスコード

import sys
N,K=map(int,sys.stdin.readline().split())
li=list(map(str,sys.stdin.readline().strip()))
cnt=0
for i in range(N):
    if li[i]=='P':
        minid=max(0,i-K)
        maxid=min(i+K,len(li)-1)
        for k in range(minid,maxid+1):
            if li[k]=='H':
                cnt+=1
                li[k]='0'
                break
print(cnt)
しかし、最初に作成したコードで完成させたいので、既存のコードから不要な部分を削除し、コードを修正しました.最初のコードは入力配列で参照されなくなったすべての要素の値を変更し、今回は参照する区間を設定し、条件に合致する要素の値だけを変更しました.

タイムアウトコードを変更して成功したコード

import sys
N,K=map(int,sys.stdin.readline().split())
cnt=0
perli=list(map(str,sys.stdin.readline().strip()))
for i in range(len(perli)):
    if perli[i]=='P':
        if i-K>=0:
            if i+K>=len(perli):
                for x in range(i-K,len(perli),1):
                    if perli[x]=='H':
                        perli[x]=0
                        cnt+=1
                        break
            else:
                for x in range(i-K,i+K+1):
                    if perli[x]=='H':
                        perli[x]=0
                        cnt+=1
                        break
        else:
            for y in range(0,i+K+1):
                if y>=len(perli):break
                elif perli[y]=='H':
                        perli[y]=0
                        cnt+=1
                        break  
print(cnt)
青少年JS開発者が学ぶRust-(2)
関数におけるreturnの省略プロセス