算法设计与分析数据结构与算法实验5：找新数最小的删除方案

算法设计与分析/数据结构与算法实验5：找新数最小的删除方案

这里写目录标题

1.实验目的2.实验内容

(1)问题描述(2)输入(3)输出 3.问题实例分析4.算法描述及说明5.算法正确性分析6.算法时间复杂性分析7.运行结果展示及其说明8.心得体会9.程序源代码

1.实验目的

(1)掌握贪心算法的处理思路与算法框架。
(2)掌握应用贪心算法解决具体问题的方法。
(3)掌握贪心算法的广泛应用。

2.实验内容 (1)问题描述

  给定一个 n n n位正整数 d d d，删除其中任意的 k ( k ≤ n ) k(k le n) k(k≤n)个数字之后，剩下的数字按照原次序排列构成一个新的正整数。对于给定的 n n n位的正整数 d d d和正整数 k k k，设计一个算法，寻找使得剩下的数字构成的新数最小的删除方案。

(2)输入

  输入包含3行。
  第一行包含一个字数字 n n n，表示正整数位数。
  第二行包含一个正整数 D D D，表示正整数的数值。
  第三行包含一个数字 k ( k ≤ n ) k(k le n) k(k≤n)，表示要删除其中 k k k位数字。

(3)输出

  输出只有一行。
  输出剩下的新数字，这个数字最小。

3.问题实例分析

  实例：输入参数 n = 7 , D = 1432159 , k = 3 n=7,D=1432159,k=3 n=7,D=1432159,k=3。
  首先，在选取了3位数字进行删除之后，剩下的数字总是4位数。同样的，对于一个 n n n位数，在选择了 k k k位数字进行删除之后，剩下的数字总是 n − k n-k n−k位。对于位数同样都是 n − k n-k n−k位的数字，可以用“字典序”对这两个数的大小进行比较。
  比较方法如下：记 m = n − k m=n-k m=n−k，对于两个 m m m位数 A A A和 B B B，可以按数位拆分成 A = a 1 a 2 a 3 . . . a n ‾ A=overline {a_1a_2a_3...a_n} A=a1​a2​a3​...an​​和 B = b 1 b 2 b 3 . . . b n ‾ B=overline {b_1b_2b_3...b_n} B=b1​b2​b3​...bn​​。先从最高位开始比较，若 a 1 < b 1 a_1 b 1 a_1>b_1 a1​>b1​，则 A > B A>B A>B。若 a 1 = = b 1 a_1==b_1 a1​==b1​，则比较第二位，即根据 a 2 a_2 a2​和 b 2 b_2 b2​的大小关系判断 A A A和 B B B的大小关系。若 a 2 = = b 2 a_2==b_2 a2​==b2​，则比较 a 3 a_3 a3​和 b 3 b_3 b3​的大小关系…依次类推，即：若高位不相等，则高位的大小关系为数字的大小关系。若高位相等，则低一位的大小关系为数字大小关系。
a i = b i , i = 1 , 2 , 3... m , a m + 1 > b m + 1 a_i=b_i,i=1,2,3...m,a_{m+1}>b_{m+1} ai​=bi​,i=1,2,3...m,am+1​>bm+1​
  记数字 D = d 1 d 2 d 3 d 4 d 5 d 6 d 7 ‾ = 1432519 D=overline {d_1d_2d_3d_4d_5d_6d_7}=1432519 D=d1​d2​d3​d4​d5​d6​d7​​=1432519
  例如，如果我们要删1个数字，我们有7种删法，把数删成432519 / 132519 / 143519 / 143259 / 143519 / 143251。显然，132519是最优解，删掉了第二位上的4这个数字。原数是1432519。
  之所以删掉第二位上的4这个数字，是因为 d 1 = 1 , d 2 = 4 , d 3 = 3 d_1=1,d_2=4,d_3=3 d1​=1,d2​=4,d3​=3，满足 d 1 < d 2 > d 3 d_1d_3 d1​d3​。所以， d 1 d 3 ‾ < d 1 d 2 ‾ < d 2 d 3 ‾ overline{d_1d_3}   可以对这一删除数字的策略加以推广。从前往后遍历数字（即从高位往低位读取数字），若还能再删数字，则最先删掉满足 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的第一个 d i d_i di​。因为， d 1 . . . d i − 1 d i + 1 . . . d n ‾ < d 1 . . . d i − 1 d i . . . d n ‾ < d 1 . . . d i d i + 1 . . . d n ‾ overline {d_1...d_{i-1}d_{i+1}...d_n}   以原问题为例。在上文中，我们已经 n = 7 , D = 1432519 , k = 3 n=7,D=1432519,k=3 n=7,D=1432519,k=3把化为了 n = 6 , D = 132519 , k = 2 n=6,D=132519,k=2 n=6,D=132519,k=2。同样的，我们删除满足 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的第一个 d i d_i di​，其中， i = 2 , d i = 3 i=2,d_i=3 i=2,di​=3。剩余数字 D = 12519 D=12519 D=12519。
  接下来，重复这一过程，从左到右遍历数，删除满足 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的第一个 d i d_i di​。此时，问题被化为 n = 5 , D = 12519 , k = 1 n=5,D=12519,k=1 n=5,D=12519,k=1。 i = 3 , d i = 5 i=3,d_i=5 i=3,di​=5。将该位数字删除，最后得到： D = 1219 D=1219 D=1219。
  此时， n = 4 , D = 1219 , k = 0 n=4,D=1219,k=0 n=4,D=1219,k=0，这就是删完 k k k位数字后剩下的最小数字。
  在本问题实例中还未覆盖如下两种情况。
  第一种情况：从最高位开始， d 1 > d 2 d_1>d_2 d1​>d2​。此时，我们只要直接删除 d 1 d_1 d1​即可。
  第二种情况： d n − 1 < d n d_{n-1}   事实上，用上文的办法删除每一个符合 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的 d i d_i di​后，若仍然还要删除数字，即此时 k > 0 k>0 k>0，则此时当前数字必定满足 D = d 1 d 2 . . . d n ‾ D=overline{d_1d_2...d_n} D=d1​d2​...dn​​且 d 1 ≤ d 2 ≤ . . . ≤ d n d_1 le d_2 le ... le d_n d1​≤d2​≤...≤dn​。
  因为每次都要反复扫描、遍历数字，每次都得找到满足 d i − 1 < d i < d i + 1 d_{i-1}   用栈维护答案序列。栈中元素表示：截止到当前位置，删除不超过 k k k个数字后，所能得到的最小整数。在删除 k k k次数据之前，栈中序列从栈底到栈顶单调不下降。
基于前文贪心算法的思想，对于每个数字 d i d_i di​，如果该数字 d i d_i di​小于栈顶元素，则不断将栈顶元素出栈，即将栈顶的数字删除。直到：
  （1）已经把 k k k个数字的删除次数用完；
  （2）栈为空，即把 d i d_i di​删成当前剩余数字的最高位；
  （3）栈顶数字小于等于当前数字，即为找到了当前满足 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的 d i d_i di​。在把 k k k次删数字机会全用完之前，栈中存储的数字总是满足： d 1 ≤ d 2 ≤ . . . ≤ d i d_1 le d_2 le ...le d_i d1​≤d2​≤...≤di​。
  例如，对原问题 n = 7 , D = 1432519 , k = 3 n=7,D=1432519,k=3 n=7,D=1432519,k=3，利用单调栈可以如此解决：

  初始时，将1和4入栈。3<4，则3入栈，4出栈，把4删除。

  3入栈后，1<3.下一位数字为2,2<3。所以，需要将3出栈，并删除3。

  2入栈后，1<2。下一位数字为5。2<5。所以，5入栈。此时，就是满足 d 1 ≤ d 2 ≤ d 3 d_1 le d_2 le d_3 d1​≤d2​≤d3​。但是，5入栈后，下一位数字为1。1<5。所以，需要将1出栈，并删除5。

  1入栈后，尽管2>1，但是此时删除数字的次数已经被用光了，所以不能将2出栈并删除，而是将剩下的数字全部直接入栈。

  在上述流程结束后还需要特判考虑一些特殊情况。
  如果删掉 m m m了个数字且 m < k m 4.算法描述及说明

  正如第3节问题实例分析所述，算法的整体流程如下：
  1.输入数据，这个数据用数组的形式进行存储，数组的每一位表示原数字的每一位。
  2.创建一个栈，将最高位数入栈。
  3.遍历数字的每一位，若当前位数字小于栈顶元素，则将栈顶的数出栈并删除。直到栈为空，或 k k k个数字的删除次数被用完，或直到新的栈顶元素小于等于当前位数字。
  4.特判特殊情况：删掉过 m m m个数字且 m < k m   5.将删完后的新数字进行输出。

5.算法正确性分析

  算法会正确地结束：在遍历完每一位数字后，算法会停止。
  符合贪心算法的基本要素：贪心选择性质。问题的整体最优解可以通过局部最优解得到。正如上文所述，若能删数字，则最先删掉满足 d i − 1 < d i > d i + 1 d_{i-1}d_{i+1} di−1​di+1​的第一个 d i d_i di​。因为， d 1 . . . d i − 1 d i + 1 . . . d n ‾ < d 1 . . . d i − 1 d i . . . d n ‾ < d 1 . . . d i d i + 1 . . . d n ‾ overline {d_1...d_{i-1}d_{i+1}...d_n}   符合贪心算法的基本要素：最优子结构性质。问题的子问题为给定一个 n n n位整数，删去其中 k − 1 k-1 k−1位数字后，剩下的最小数字。该问题的最优解是包含子问题最优解的，所以符合最优子结构性质。
  利用反证法对算法的正确性进行证明：记原数字为 A = a 1 a 2 . . . a n ‾ A=overline{a_1a_2...a_n} A=a1​a2​...an​​，删除 k k k位数字后剩下的最小数为 D ′ = d 1 d 2 . . . d n − k ‾ D'=overline{d_1d_2...d_{n-k}} D′=d1​d2​...dn−k​​。首先假设由该策略删除数字剩下的数字不是最小的，即存在这么一个数 P = p 1 p 2 . . . p n − k ‾ P=overline{p_1p_2...p_{n-k}} P=p1​p2​...pn−k​​,显然 P = p 1 p 2 . . . p n − k ‾ P=overline{p_1p_2...p_{n-k}} P=p1​p2​...pn−k​​的字典序小于 D ′ = d 1 d 2 . . . d n − k ‾ D'=overline{d_1d_2...d_{n-k}} D′=d1​d2​...dn−k​​， p 1 < d 1 p_1 6.算法时间复杂性分析

   算法中只需要遍历一次数字各位。数字有 n n n位。尽管存在嵌套循环，但是内部最多循环 k k k次， 0 < k ≤ n 0 7.运行结果展示及其说明

测试样例使用了两组。对于每一组测试样例，都能正确地根据数字的位数 n n n、数值 D D D、要删除的位数 k k k生成数值最小的新数。

8.心得体会 9.程序源代码

#include
#include
#include
#include
int d[20];//一个数最多18位
using namespace std;
int main() {
	int n,k;
	long long D;
	cin >> n;
	cin >> D;
	cin >> k;
	long long temp = D;
	for (int i = n; i >= 1; i--) {
		d[i] = temp % 10;
		temp = temp / 10;
	}
	vector stk;
	for (int i = 1; i <= n; i++) {
		while (stk.size() > 0 && stk.back() > d[i] && k > 0) {
			k--;
			stk.pop_back();
		}
		stk.push_back(d[i]);
	}
	for (; k > 0; k--)
		stk.pop_back();
	long long ans = 0;//新数字
	for (int i = 0; i < stk.size(); i++) {
		ans = ans * 10;
		ans += stk[i];
	}
	cout << ans;
	return 0;
}