题解：UVA11491 奖品的价值 Erasing and Winning

_WHX985_ · 2025-01-13 15:04:53 · 题解

思路分析

作为一道黄题，暴力搜索是肯定不行的，所以考虑用其他算法。数学好的人可能已经看出这道题用贪心。那么怎么贪心？多举几个例子就会发现，我们可以从开头扫到 n-1 号位，每当一个数小于前一个数就删了，否则删前一个，如果在删掉的中途没次数了就结束整个过程。

估算时间复杂度

扫一遍时间复杂度为 O(n)，再查找一遍时间复杂度为 O(n-k)，所以总时间复杂度为 O(2n-k)。

易错点

代码停止条件易错，请务必认真仔细。

代码实现

AC 代码

#include<bits/stdc++.h>
#define WHX985 return
#define code 0
using namespace std;
int f[1000005];
bool vis[1000005];
int main(){
    while(1){
        int n,k;
        cin>>n>>k;
        if(n==0&&k==0){
            return 0;
        }
        string a;
        cin>>a;
        for(int i=0;i<=a.size()-1;i++){
            f[i]=a[i]-'0';
            vis[i]=0;
        }
        int jk=0;
        for(int i=0;i<=a.size()-1;i++){
            if(jk==k-1)break;
            if(vis[i]){
                continue;
            }
            if(f[i+1]<f[i]){
                jk++;
                vis[i+1]=1;
            }else{
                jk++;
                vis[i]=1;
            }
        }
        int nao=0x7ffffff,minn;
        for(int i=0;i<a.size();i++){
            if(vis[i])continue;
            if(nao>f[i]){
                nao=f[i];
                minn=i;
            }
        }
        vis[minn]=1;
        for(int i=0;i<=a.size()-1;i++){
            if(!vis[i]){
                cout<<f[i];
            }
        }
        cout<<'\n';
    }

    WHX985 code;
}
//100000
//587854740865
// 8 8  7 0865
//8874086