贪心--删数问题

    科技2022-09-05  141

    贪心–删数问题

    题目大意: 键盘输入一个高精度的正整数N(不超过250位) ,去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和k,寻找一种方案使得剩下的数字组成的新数最小。

    输入格式 n (高精度的正整数) k(需要删除的数字个数)

    输出格式 最后剩下的最小数。

    输入输出样例 输入 175438 4

    输出 13

    解题思路: 首先,我们先举一个例子:

    1 7 5 4 3 8

    删的个数:4

    不难看出:

    第一次删的应该是 7

    第二次删的应该是 5

    第三次删的应该是 4

    第四次删的应该是 8

    那么,剩下的数就是“13”(经过比较发现确实正确)

    是如何得出规律的呢?? 我们仔细观察一下这个例子:

    第一次删的数为7,和5比较,发现7跟大(简单表述)

    第二次删的数为5,和4比较,发现5跟大

    第三次删的数为4,和3比较,发现4跟大

    第四次删的数为8,和最后一个数(应该是a[7](假设有,并为0))比较,发现5跟大

    大家有木有发现规律?? 很明显,就是删去下坡数,也就是这个例子中的7(比5大)、5(比4大)、4(比3大)、8(比最后一个大(假设有,并为0))。

    #include<bits/stdc++.h> using namespace std; string st; int n,a[251],l; int main() { cin >> st; cin >> n; l=st.size(); for(int i = 0;i < l;i++) a[i] = st[i] - '0'; for(int i = 1;i<= n;i++) for(int j = 0;j < l;j++) if(a[j] > a[j + 1]) { for(int r = j;r < l;r++) a[r]=a[r + 1]; l--;break; } int i = 0,k = 0; while(a[i] == 0 && k < l - 1) k++,i++; for(int i = k;i < l;i++) cout<<a[i]; return 0; }
    Processed: 0.009, SQL: 9