--- title: 删数问题，贪心策略 url: 'https://yayi.site/archives/删数问题贪心策略' categories: 算法与设计 cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/犬吠·埼 樹.png' abbrlink: 60c2aa67 date: 2019-10-19 22:57:53 updated: 2021-05-14 22:04:52 tags: ---  #### 一、 !\[在这里插入图片描述\](http://img.yayi.site/csdn/20191019225742685.png-watermaskStyle) 思路：解：应用贪心算法设计求解 （1） 设计要点 操作对象为n位高精度数，存储在数组a中。 在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。 每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。 当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部降序或相等，则删除左边的大数字。 当k\>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。 若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。 ##### 二、伪代码： !\[在这里插入图片描述\](http://img.yayi.site/csdn/20191019225810818.png-watermaskStyle) ##### 三、源代码 ==核心的是deleck函数==，main输入输出，erase删除传过来的指针所指向的数，没有什么的。 为什么不用数组，数组不能删除元素，要加很多判定条件。代码很难理解 ，。链表使 deleck 更接近伪代码结构。 a.size就是所剩的元素。你可以用java写，这样操作链表容易一点。 \`\`\`cpp // 删数问题贪心策略.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //earase:抹去；擦除 #include //贪心策略：最近下降点优先 int n = 6;//位数 int k=4;//删掉的位数 //int a\[n\] = {1,7,8,5,4,3};//整数 typedef struct list{ struct list\* last; int a; struct list\* next; }LNode,\*LinkList; void erase(LNode \*p,LinkList link) { LinkList q=link; LNode \*r; if (p == link) { if (link-\>next == NULL) { link = NULL; return; } link = p-\>next; free(q);//删除q; } if (p-\>next == NULL) { p-\>last-\>next = NULL; free(p); } else { r = p; r-\>last -\>next= r-\>next; r-\>next-\>last = r-\>last; free(p); } } //源码 void delek(LinkList link) { LNode\* q; q = link;//q指向了开头 int m = n; if (k \>= m) { std::cout \<\< "全删除"; return; } while (k \> 0) { for (int i = 0; (i \< m - 1) \&\&((q-\>a )\<= (q-\>next-\>a)); i++) { erase(q-\>next, link); k--; m--; } } while (m \> 1 \&\& link-\>a == 0) erase(link, link); } void createLinkF(LinkList \* L, int a) { LinkList p; p =(LinkList)malloc(sizeof(LNode)); p-\>a = a; p-\>next = NULL; p-\>last = \*L; (\*L)-\>next = p; } int main() { LinkList link; link = (LinkList)malloc(sizeof(LNode)); link-\>last = NULL; std::cout \<\< "n:"\<\> n;//输入位数 std::cout \<\< "a的每位数" \<\< std::endl; std::cin \>\> link-\>a;//第一位搞定先 int y = 2; int num; LinkList p = link; while (y \<= n) { std::cin \>\> num; createLinkF(\&p, num); p = p-\>next; y++; } std::cout \<\< "k:" \<\> k; //删数 delek(link); LinkList e = link; while (e != NULL) { if (e-\>next != NULL) { std::cout \<\< link-\>a \<\< " "; e = e-\>next; } else { std::cout \<\< e-\>a; break; } } } \`\`\`