uva 11491:Erasing and Winning(贪心)

题意:给一个长n(n<10^5)位的数,删除d位,求删除后最大的数。(原数无前导0)

思路:从前往后扫,如果a[i] > a[i-1],则删除a[i-1]。我暴力的用链表实现了……

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
using namespace std;

#define N 100020
char str[N];
int main() {
    int n, d;
    while (scanf("%d%d",&n, &d) != EOF) {
        if (n == 0 && d == 0) break;
        scanf("%s", str);
        list<int> num;
        num.push_back(10);
        for (int i = 0; str[i]; i++) {
            num.push_back(str[i]-0);
        }
        num.push_back(10);

        list<int>::iterator hd, ed, tmp;
        hd = num.begin();
        ed = num.begin();
        hd++;
        while (d) {
            if (*hd > *ed) {
                num.erase(ed);
                hd--;
                ed = hd;
                hd++;

                d--;
            } else {
                hd++;
                ed++;
            }
        }
        num.pop_front();
        num.pop_back();
        for (hd = num.begin(); hd != num.end(); hd++) {
            printf("%d", *hd);
        }
        puts("");
    }
    return 0;
}

                

 然而实际上,可以一边输入一边处理(笨笨的)

别人的代码:

#include <cstdio>

int n,m,a;
int t,s[100009];

int main()
{
    LOOP:
    {
        scanf("%d%d%*c",&n,&m);
        if (n==0 && m==0) return 0;
        m=n-m;
        t=0;
        for (int i=0;i<n;++i)
        {
            a=getchar()-0;
            while (t && t+n-i>m && a>s[t-1]) --t;
            if (t<m) s[t++]=a;
        }
        for (int i=0;i<t;++i) printf("%d",s[i]);
        putchar(\n);
    }
    goto LOOP;
}

 

uva 11491:Erasing and Winning(贪心)

上一篇:Windows Phone 7 问题总结


下一篇:[Bug]CS0016: 未能写入输出文件“c:\Windows\Microsoft.NET\Framework\v4.0.30319\Temp