題意：有一個n位整數（不以0開頭），要求刪除其中的d個數字，使結果盡量大。(1<=d<n<=10^5)

分析：

1、從頭掃一遍，如果當前填的數字小于n-d，則將當前數字填上。

2、如果已經的填的數字個數加上當前位置及其后的所有數字個數>n-d，即在當前位置上還有足夠多的數可以填寫，即cnt + (n-i) > n - d，則刪除數組ans中比當前數字小的數字，因為要保證，最后剩的n-d位數的高位盡可能大。

#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) ((a < b) ? a : b) #define Max(a, b) ((a < b) ? b : a) typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 1e5 + 10; const int MAXT = 10000 + 10; using namespace std; char ans[MAXN]; int main(){int n, d;while(scanf("%d%d", &n, &d) == 2){if(!n && !d) return 0;getchar();int cnt = 0;for(int i = 0; i < n; ++i){char c = getchar();while(cnt > 0 && cnt + d - i > 0 && ans[cnt] < c){--cnt;}if(cnt < n - d){ans[++cnt] = c;}}ans[++cnt] = '\0';printf("%s\n", ans + 1);}return 0; }

　　

轉載于:https://www.cnblogs.com/tyty-Somnuspoppy/p/6375835.html

總結

以上是生活随笔為你收集整理的UVA - 11491 Erasing and Winning(奖品的价值)(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。