PTIT125I - Xóa Chữ Số - E16CN PTIT

Trang chủ » Xóa K Chữ Số để được Số Bé Nhất Pascal » PTIT125I - Xóa Chữ Số - E16CN PTIT

Có thể bạn quan tâm

E16CN PTIT

Menu
  • Tin Tức
  • Series
    • Data Structures And Alogrithms
  • Lập Trình
    • Unity
    • Web
    • Android
    • iOS
  • CMCN 4.0
    • AI
    • IoT
    • Big Data
  • Game
  • Tiếng Anh
    • TOEIC
    • IELTS
    • TOEFL
  • Tài Liệu
E16CN PTIT C++ Phát Triển PTIT SPOJ Stack PTIT125I - Xóa chữ số PTIT125I - Xóa chữ số Thứ Năm, tháng 12 14, 2017 C++ Phát Triển PTIT SPOJ Stack
Link Sub: http://www.spoj.com/PTIT/problems/PTIT125I/ Người Gửi: Dương Lee

  • Problem:

Cho một số có N chữ số. Bạn hãy xóa đi K chữ số để được số còn lại sau khi xóa là lớn nhất có thể. Input - Dòng 1: số N và K (1<=K<N<=500 000). - Dòng 2: Số có N chữ số, bắt đầu bằng số khác 0. Output - Số lớn nhất có thể sau khi xóa K chữ số. Example: Input 4 2 1924 Output: 94

  • Solution:

Nhận thấy khi xóa đi mà số vẫn lớn nhất thì mỗi lần xóa một chữ phải tạo ra số lớn nhất. VD: 1924 -> Xóa lần 1 -> 924 max -> Xóa lần 2 -> 94 max. Vậy áp dụng stack để tạo dãy tuyến tính không tăng (khi còn xóa được). Dãy đó luôn là dãy lớn nhất có thể tạo được khi xóa. EX: 170803 (K=3) S: 1 (K=3) S: 7 (K=2 (xóa 1)) S: 7 0 (K=2) S: 8 (K=0 (xóa 7, 0)) S: 8 0 (K=0) S: 8 0 3 (K=0) -> 803 max.

  • Code:

C++:

https://ideone.com/8ZXdyM
#include <iostream> #include <stack> #include <vector> using namespace std; int main () { long N, K; cin>>N>>K; stack <int> S; for (long i=1; i<=N; i++) { char tmp_char; cin>>tmp_char; int tmp_int = tmp_char - '0'; if (S.empty()) { S.push(tmp_int); } else { while (!S.empty() && tmp_int > S.top() && K>0) { S.pop(); K--; } S.push(tmp_int); } } while (K>0 && !S.empty()) { S.pop(); K--; } vector <int> smallest; while (!S.empty()) { int tmp=S.top(); S.pop(); smallest.push_back(tmp); } for (long i=smallest.size()-1; i>=0; i--) cout<<smallest[i]; return 0; }

JAVA:

DL

Author : DL

Share this

Related Posts

Next « Prev Post Previous Next Post » Đăng ký: Đăng Nhận xét (Atom)

Status

- Để đảm bảo tốc độ load trang: Web sẽ dùng "text" thay vì sử dụng "embed" cho việc hiển thị code. Điều này dẫn đến việc "có thể cósai sót" trong việc hiển thị code. Vậy nên nếu có lỗi bạn có thể sử dụng "link view" đã đính kèm sẵn và báo lỗi ngay comment.
- Loading... Up/350+ Done/700+ SPOJ PTIT

Tiện Ích

  • Yêu Cầu Giải Đáp
  • Thắc Mắc, Góp Ý, Báo Lỗi

Giải thuật và Cấu trúc dữ liệu

Toán 84 Xâu 37 Mảng Đánh Dấu 23 Quy Hoạch Động 16 Sắp Xếp 15 Sinh 13 Tham Lam 8 BFS 7 Stack 7 Tìm Kiếm Nhị Phân 6 Đệ Quy 6 Đồ Thị 6 DFS 5 Quay Lui 4 Quy Luật 4 Sàng nguyên tố Eratosthenes 3 Sắp Xếp Nổi Bọt 3 Queue 2 Danh Sách Liên Kết Kép 1 Kruskal 1 Map 1 Nhánh Cận 1 Phân Tập 1

Ngôn ngữ

C++ (190) C (23) Python (2) Java (1)

Trang luyện tập

  • PTIT SPOJ (205)
  • VN SPOJ (5)

Bài đăng HOT

  • C11PAIRS - Đếm cặp C11PAIRS - Đếm cặp
  • KPLANK - Bán dừa KPLANK - Bán dừa
  • P155SUMD - ROUND 5D - Chỉ là sắp xếp
  • DTTUI1 - Cái túi 1
  • Bảng quy đổi điểm Tiếng Anh và quy định miễn học, miễn thi, chuyển đổi điểm PTIT Bảng quy đổi điểm Tiếng Anh và quy định miễn học, miễn thi, chuyển đổi điểm PTIT
  • P145PROI - ROUND 5I - Mật khẩu
  • PTIT127C - Bố trí phòng họp PTIT127C - Bố trí phòng họp
  • BCPARTI - Partition thuận nghịch đệ quy

Cấp độ

  • Luyện Tập (150)
  • Phát Triển (40)
  • Nhập Môn (20)

Lưu trữ

Lưu trữ tháng 12 2020 (3) tháng 11 2020 (1) tháng 5 2019 (1) tháng 4 2019 (3) tháng 3 2019 (2) tháng 9 2018 (2) tháng 7 2018 (7) tháng 6 2018 (2) tháng 5 2018 (2) tháng 4 2018 (8) tháng 3 2018 (1) tháng 2 2018 (4) tháng 1 2018 (17) tháng 12 2017 (171)

Tổng số lượt xem trang

Từ khóa » Xóa K Chữ Số để được Số Bé Nhất Pascal