寻找最大数
时间限制：1000 ms  |  内存限制：65535 KB
难度：2
描述
请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大，

比如当n=92081346718538，m=10时，则新的最大数是9888

 

输入
第一行输入一个正整数T，表示有T组测试数据
每组测试数据占一行，每行有两个数n,m（n可能是一个很大的整数，但其位数不超过100位，并且保证数据首位非0，m小于整数n的位数）
输出
每组测试数据的输出占一行，输出剩余的数字按原次序组成的最大新数
样例输入
2
92081346718538 10
1008908 5
样例输出
9888
98

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string n;
        int m;
        cin>>n>>m;
        sort(n.begin(),n.end());
        for(int i=n.length()-1;i>=m;i++)
            cout<<n[i]-'0';
        cout<<endl;
    }
    return 0;
}

解决了，，刚开始没注意题目要求

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int m;
        string n;
        cin>>n>>m;
        int len=n.length();
        int t1=0,temp=m;
        
        for(int i=0;i<len-m;i++)
        {
            int j;
            char Max;
            for(j=t1,Max=n[t1];j<=temp;j++)
            {
                if(n[j]>Max)
                {
                    Max=n[j];
                    t1=j;
                }
            }
            cout<<Max;
            temp++;
            t1++;
        }
        cout<<endl;
    }
    return 0;
}

取消排序

应该是方法问题,排序从大到小取不一定是正确结果,例如911819这样取其中三个数应该是989,但排序后变成了998,题目强调了是原次序~更何况排序本身就会超时(这题数据较小还说得过去)~

简单说就是用优先队列,从最低位开始取,队列没有饱和的时候遇见元素进队并设置当前最大元素MAX,队列饱和的时候遇到大于等于MAX的进队并更新MAX,并且通过优先队列对堆顶元素进行出队,这样算法复杂度为o(n*log(n))看见数据范围大小100应该允许时间复杂度为o(n^2)甚至是o(n^3)的算法吧~

[此贴子已经被作者于2018-3-29 15:29编辑过]

看出来就是每次遍历一次数组取最大的一位,然后下一次直接遍历前面部分,简单容易理解,算法复杂度为o(n^2);
笑了

吃瓜去~

新手上路多谢指导