11070. Xóa Chữ Số | Lập Trình C/C++

Trang chủ » Xóa K Chữ Số để được Số Lớn Nhất C » 11070. Xóa Chữ Số | Lập Trình C/C++

Có thể bạn quan tâm

Menu Bỏ qua nội dung

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

Ý tưởng

Giả sử n có d chữ số dùng đệ quy giải bài toán

  • Nếu k=0 thì giữ nguyên n
  • Nếu k > 0 thì ta giữ tìm max  trong phần d-k chữ số nửa đầu để bắt đầu giữ lại để sau khi xóa đi đoạn đầu chữ thì vẫn phải đủ d-k chữ số sau đó gọi đệ quy xử lý xóa chỗ còn lại tùy theo số chữ số đã được xóa

Nguồn

http://www.spoj.com/PTIT/problems/PTIT125I/

Code

http://ideone.com/b5t7DZ

long N,d=0; char *q,*p; void xoa(long k,char *x) { if(k==0) printf("%s",x); else if(d==N-k) return; else { q=x; for(p=x+1;p<=x+k;p++) { if(*q<*p) q=p; if(*q=='9') break; } printf("%c",*q); d++; xoa(k-(q-x),q+1); } } int main() { long k; scanf("%ld%ld",&N,&k); char *x=new char[N+3]; scanf("%s",x); xoa(k,x); }

Chia sẻ ngay:

Thích Đang tải... Điều hướng bài viết ← 11069. Chỗ ngồi 11071. Bàn cờ →

7 thoughts on “11070. Xóa chữ số”

  1. bài này e sắp xếp 1924 thành giảm dần là 9421 rồi trừ 2 số cuối đi sao vẫn sai ạ

    ThíchThích

  2. Bài này không được sắp xếp em ạ, ví dụ xóa 2 chữ số của 59362 thì còn 962

    ThíchThích

  3. thầy ơi như thầy với bạn trên kia trao đổi em không hiểu lắm, tại sao 59362 sắp xếp thành 96532, xóa 2 chữ số cuối đi lại thành 962 ạ ???

    ThíchThích

  4. 59362 nếu xoá 1 chữ số thì nó sẽ có thể sinh ra các số sau Xoá số 5 còn 9362 Xoá số 9 còn 5362 Xoá số 3 còn 5962 Xoá số 6 còn 5932 Xoá số 2 còn 5963

    Vậy xoá đi 1 chữ số ra số lớn nhất là 9362. Em làm tương tự xem xoá 2 chữ số thì ra những số nào, max là số nào. chứ không hề có sắp xếp nào

    ThíchThích

  5. em hiểu rồi ạ. Em cảm ơn thầy.

    ThíchThích

  6. xin Thầy cho xin địa chỉ mail hoặc cách liên hệ được không ah.. thanks Thầy

    ThíchThích

  7. Email của mình tichpx@yahoo.com

    ThíchThích

Bình luận về bài viết này

Δ

  • Bình luận
  • Đăng lại
  • Theo dõi Đã theo dõi
    • Lập trình C/C++
      • Đã có 26 người theo dõi Theo dõi ngay
    • Đã có tài khoản WordPress.com? Đăng nhập.
    • Lập trình C/C++
    • Tùy biến
    • Theo dõi Đã theo dõi
    • Đăng ký
    • Đăng nhập
    • URL rút gọn
    • Báo cáo nội dung
    • Xem toàn bộ bài viết
    • Quản lý theo dõi
    • Ẩn menu
%d Tạo trang giống vầy với WordPress.comHãy bắt đầu

Từ khóa » Xóa K Chữ Số để được Số Lớn Nhất C