2025 - 12 - 26 - 第 46 篇
【洛谷】貪心算法題單 - 【貪心算法】 - 【學習筆記】
作者(Author): 鄭龍浩 / 仟濹(CSND賬號名)

目錄

P1106 刪數問題

題目描述

鍵盤輸入一個高精度的正整數 $n$（不超過 $250$ 位），去掉其中任意 $k$ 個數字后剩下的數字按原左右次序將組成一個新的非負整數。編程對給定的 $n$ 和 $k$，尋找一種方案使得剩下的數字組成的新數最小。

輸入格式

輸入兩行正整數。

第一行輸入一個高精度的正整數 $n$。

第二行輸入一個正整數 $k$，表示需要刪除的數字個數。

輸出格式

輸出一個整數，最后剩下的最小數。

樣例 #1

樣例輸入 #1

175438 
4

樣例輸出 #1

13

提示

用 $\mathrm{len}(n)$ 表示 $n$ 的位數，保證 $1\le k<\mathrm{len}(n)\le 250$。

思路

刪除任意k個數字以后，如何保證是最小的數呢，如何去掉呢？？？？
思路是這樣的，從做往右(高位到低位)依次兩兩比較，如果 arr[ i ] <= arr[ i + 1 ], 則無需管，直到遇到 arr[ i ] > arr[ i + 1 ], 這時候需要將 arr[ i + 1 ] 去掉
說白了，就是盡量讓這個數字保持升序，這樣才能保證最小 --> 高位數字小 --> 則整個數字小

所以，去掉的數字一般分為兩種情況

1. 在 i ~ num - 1 的范圍內, 【有】 arr[ i ] > arr[ i + 1 ] 的清況 --> 去掉arr[ i + 1 ]
2. 在 i ~ num - 1 的范圍內, 【無】 arr[ i ] > arr[ i + 1 ] 的清況 --> 去掉最后一位 --> 為什么是去掉最后一位呢，因為數字順序為升序的時候，最右側的數字是最大的，所以去掉
   ( 第 2 種情況 也無需再單獨去判斷了，因為內層循環中如果找不到arr[ i ] <= arr[ i + 1 ]，退出循環的時候，i 會定位在 倒數第二個元素上面 )

最右側的數字相當于 --> 整個高精度正數少了一位 + 少了最大的數

程序過程：

1. 最外層循環：用來控制循環次數 --> 循環 k 次 --> 刪掉 k 個數字
2. 最內層循環：用來尋找 arr[ i ] < arr[ i + 1 ] 的情況，如果遇到，則退出循環，將 i 定位在 5 處( 比如 1 2 3 4 5 1 ),退出循環以后將 5 刪除即可

借用的函數: erase(a, b) --> 刪除函數 --> STL容器

高峰期–> 我的理解就是 從左往右依次兩兩比較，只要遇到不是 arr[ i ] <= arr[ i + 1 ] 而是 arr[ i ] > arr[ i + 1 ], 則 arr[ i ] 就是這個高峰期
簡單點說,就是盡可能的讓高位數字的順序為升序 --> 因為 高位數字小, 則整個 高精度數字 就小

變量：
arr --> 存放高精度正整數
k --> 要刪除的數字的數量
i --> 決定 高峰 的位置

代碼

// 洛谷P1106 刪數問題
// 作者: 鄭龍浩 / 仟濹(CSDN)
// 時間：2025 - 01 -22
// 鍵盤輸入一個高精度的正整數 n（不超過 250 位），去掉其中任意 k 個數字后剩下的數字按原左右次序將組成一個新的非負整數。編程對給定的 n 和 k，
// 尋找一種方案使得剩下的數字組成的新數最小。// 看的這個大佬的題解，我才會這么做的 https://www.luogu.com.cn/article/qgschm0n// 思路:
// 刪除任意k個數字以后，如何保證是最小的數呢，如何去掉呢？？？？
// 思路是這樣的，從做往右(高位到低位)依次兩兩比較，如果 arr[ i ] <= arr[ i + 1 ], 則無需管，直到遇到 arr[ i ] > arr[ i + 1 ], 這時候需要將 arr[ i + 1 ] 去掉
// 說白了，就是盡量讓這個數字保持升序，這樣才能保證最小 --> 高位數字小 --> 則整個數字小// 所以，去掉的數字一般分為兩種情況
// 1. 在 i ~ num - 1 的范圍內, 【有】 arr[ i ] > arr[ i + 1 ] 的清況 --> 去掉arr[ i + 1 ]
// 2. 在 i ~ num - 1 的范圍內, 【無】 arr[ i ] > arr[ i + 1 ] 的清況 --> 去掉最后一位 --> 為什么是去掉最后一位呢，因為數字順序為升序的時候，最右側的數字是最大的，所以去掉
// ( 第 2 種情況 也無需再單獨去判斷了，因為內層循環中如果找不到arr[ i ] <= arr[ i + 1 ]，退出循環的時候，i 會定位在 倒數第二個元素上面 )// 最右側的數字相當于 --> 整個高精度正數少了一位 + 少了最大的數、
// 程序過程：
// 1. 最外層循環：用來控制循環次數 --> 循環 k 次 --> 刪掉 k 個數字
// 2. 最內層循環：用來尋找 arr[ i ] < arr[ i + 1 ] 的情況，如果遇到，則退出循環，將 i 定位在 5 處( 比如 1 2 3 4 5 1 ),退出循環以后將 5 刪除即可//借用的函數：erase(a, b) --> 刪除函數 --> STL容器// 高峰期 --> 我的理解就是 從左往右依次兩兩比較，只要遇到不是 arr[ i ] <= arr[ i + 1 ] 而是 arr[ i ] > arr[ i + 1 ], 則 arr[ i ] 就是這個高峰期
// 簡單點說,就是盡可能的讓高位數字的順序為升序 --> 因為 高位數字小, 則整個 高精度數字 就小// 變量：
// arr --> 存放高精度正整數
// k --> 要刪除的數字的數量
// i --> 決定 高峰 的位置#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main( void ){string arr; // 表示的 高精度正整數int k; // 表示的 要刪除的數字數量cin >> arr >> k;while( k ){// 尋找 高峰期int i;for( i = 0; arr[ i ] <= arr[ i + 1 ] && i < arr.size() - 1; i ++ ); // 非常簡潔 --> 尋找 高峰期(第一次知道這個詞語，從題解中看到的，因為我自己不知道用什么詞語可以表達找到的這個元素)arr.erase( i, 1 ); // 從第 i 個位置連續刪 1 個元素k --;}// 處理前導零 --> 如果本來的 高精度正整數 前面幾個為0,則不能將其打出來, 應該將它們去掉while( arr [ 0 ] == '0' && arr.size() > 1 ) {//處理前導零, 并且保證如果數字為0,則必須保留一位0 arr.erase( 0, 1 );}cout << arr;return 0;
}