首页 > 代码库 > uva 11491:Erasing and Winning(贪心)
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 100020char 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(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。