删数问题，贪心策略-删数问题贪心策略

title: 删数问题，贪心策略
url: 'https://yayi.site/archives/删数问题贪心策略'
categories: 算法与设计
cover: 'https://cdn.jsdelivr.net/gh/TangxinGH/picbed/img/动漫/結城友奈は勇者である/犬吠·埼 樹.png'
abbrlink: 60c2aa67
date: 2019-10-19 22:57:53
updated: 2021-05-14 22:04:52

tags:



一、

思路：解：应用贪心算法设计求解
（1） 设计要点
操作对象为n位高精度数，存储在数组a中。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部降序或相等，则删除左边的大数字。
当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。

二、伪代码：

三、源代码

==核心的是deleck函数==，main输入输出，erase删除传过来的指针所指向的数，没有什么的。
为什么不用数组，数组不能删除元素，要加很多判定条件。代码很难理解 ，。链表使 deleck 更接近伪代码结构。
a.size就是所剩的元素。你可以用java写，这样操作链表容易一点。

// 删数问题贪心策略.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//earase:抹去；擦除

#include <iostream>

//贪心策略：最近下降点优先
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:"<<std::endl;
    std::cin >> 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:" <<std::endl;
    std::cin >> 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;
        }
    }

}