HDU3183- 贪心

超、凢脫俗 2022-07-11 01:50 111阅读 0赞

# A Magic Lamp #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3728    Accepted Submission(s): 1515**

Problem Description

Kiki likes traveling. One day she finds a magic lamp, unfortunately the genie in the lamp is not so kind. Kiki must answer a question, and then the genie will realize one of her dreams.   
The question is: give you an integer, you are allowed to delete exactly m digits. The left digits will form a new integer. You should make it minimum.  
You are not allowed to change the order of the digits. Now can you help Kiki to realize her dream?

Input

There are several test cases.  
Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero.

Output

For each case, output the minimum result you can get in one line.  
If the result contains leading zero, ignore it.

Sample Input

178543 4 
    1000001 1
    100001 2
    12345 2
    54321 2

Sample Output

13
    1
    0
    123
    321

题目大意：给你一串数字，让你从中删除m个使得剩下的数字串字典序最大并且输出该数字串（不含前导0）

题目思路：现在假设数字串是递增的：如 123456  显然这时要从后面开始删除  ，假设递减：如  54321 显然要从头开始删除   ，，如果不是单调的呢？那我们可不可以构造

成单调的呢，当然可以，我们先拿数字串的前两个数字来想，显然两个是单调的，如果前面的比后面的大那就先要删除第一个，否则先保留，这里可以用栈来存

每次都拿栈顶的数字与后面的数字比较，大就要出栈，否则入栈，这样就维护了一个单调递增栈，最后如果m>0就一次出栈直到m=0，

贪心的正确性为：从头开始就维护了一个单调递增的序列，所以不存在另外一个序列的字典序更小！

AC代码:

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<stack>
    using namespace std;
    
    int main()
    {
        char s[1005];              //存数字串
        int m;
        while(~scanf("%s %d",s,&m)){
            int len = strlen(s);
            stack<int>st;              //维护单调递增序列
            for(int i=0;i<len;i++){
                int x = s[i]-'0';
                if(st.empty()||m==0){    //不需要删除了或栈为空
                    st.push(x);
                }
                else {
                    while(!st.empty()&&st.top()>x&&m){   //栈顶的数字大于后面的数字
                        st.pop();
                        m--;
                    }
                    st.push(x);
                }
            }
            while(m&&!st.empty()){        //m>0 栈单调递增，依次出栈
                st.pop();
                m--;
            }
            int ans[1005],cnt = 1000;
            ans[1000]=0;
            while(!st.empty()){                  //处理栈中的数字序列
                ans[cnt--]=st.top();
                st.pop();
            }
            while(++cnt<=1000&&ans[cnt]==0);
            if(cnt==1001)printf("0\n");
            else {
                for(;cnt<=1000;cnt++)printf("%d",ans[cnt]);
                printf("\n");
            }
        }
        return 0;
    }