Xâu min
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho xâu \(S\) chứa các kí tự \(1 \ldots 9\) (\(|S| \leq 1000\) kí tự) và số nguyên \(K\) (\(1 \leq K \leq |S|\)). (\(|S|\) độ dài của xâu \(S\))
Yêu cầu: Chọn \(K\) kí tự trong xâu \(S\) theo thứ tự ban đầu để tạo thành số \(X\) gồm \(K\) chữ số có giá trị bé nhất.
Input
- Dòng 1: Ghi số \(K\).
- Dòng 2: Ghi xâu \(S\).
Output
- Ghi một số duy nhất \(X\).
Example
Test 1
Input
3
89678982 Output
672
Bình luận
def smallest_number(K, S):
stack = []
n = len(S)
Đọc dữ liệu từ đầu vào
import sys
input = sys.stdin.read
data = input().split()
K = int(data[0])
S = data[1]
Tính kết quả và in ra
print(smallest_number(K, S))
ý tưởng dành cho bạn nào thích dp :
suy ra ta có công thức dp như sau :
TH 1 : chọn số thứ i + 1 : dp[i + 1][j + 1] = min(____,dp[i][j] + s[i + 1]) , điều kiện : j + 1 <= k
TH 2 : không chọn số thứ i + 1 : dp[i + 1][j] = min(____,dp[i][j])
code mẫu cho bạn nào còn : https://ideone.com/CIbbBz
python:
k = int(input())
s = input()
l = len(s) - k + 1
r = 0
ds = []
for i in range(1, k + 1):
so = 10
n = 0
for j in range(r, l):
if int(s[j]) < so:
so = int(s[j])
n = j
l += 1
r = n + 1
ds.append(str(so))
kq=""
for i in ds:
kq+=i
print(kq)
bài này dùng stack vẫn được mà đk mn
sao sai vay ban
ngôn ngữ gì vậy N7hoatt
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
1 bình luận nữa