HDU3183 A Magic Lamp —— 贪心（单调队列优化）/ RMQ / 线段树

时间：2024-11-28 18:05:56

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3183

题解：

方法一：贪心。

在草稿纸上试多几次可以知道，删除数字中从左到右最后一位递增（可以等于）的数字，可以得到最小值，在这个基础下，又继续删除最后一位递增的数字，得到的依然是最小值。这就表明当前这步的贪心不仅是当前最优，而且对于下一步贪心来说也是最优的。所以每次删除最后递增项就可以了。

初期代码（每次循环找最后递增项）：

Accepted 3183 46MS 1408K 1259 B G++ 
#include<cstdio>//hdu3183 贪心，删除不严格递增序列的最后一个元素

#include<cstring>

#include<algorithm>

#define MAX(a,b) (a>b?a:b)

#define LL long long

#define mod 1000000007

using namespace std;

int main()

{

    int n,m;

    char dig[1005],ans[1005];

    while(scanf("%s%d",dig,&m)!=EOF)

    {

        n = strlen(dig);

        if(n<=m)

        {

            puts("0");

            continue;

        }

        for(int i = 0; i<m; i++)

        {

            //每次从头开始找递增序列的最后一个元素

            int j = 0,last = 0,de = 0;

            for(j = 1;j<=n-1; j++)

            {

                if(dig[j]==0) continue;

                if(dig[last]<=dig[j])//用last记录上次的最后一个递增元素，以便跳过已经被删除的元素

                    last = j;

                else break;

            }

            dig[last] = 0;//将递增序列的最后一个元素标记，删除

        }

        int cnt = 0;

        for(int i = 0; i<n; i++)//将未被删除的导入数组中，

            if(dig[i]) ans[cnt++] = dig[i];

        int j = 0;

        while(j<cnt-1 && ans[j]=='0')//跳过前导0，但要留最后一位，因为答案可能就为0

            j++;

        while(j<cnt)

            putchar(ans[j++]);

        putchar('\n');

    }

    return 0;

}

后来发现:每一次都循环找出递增项，其实已经重复操作了。因为在上一次删除中，前面的数字肯定是递增的，这就不用再重新扫一次了，只需要判断当前数字是否也递增，如果递增，则继续下一个数字，如果不是，则将前面的数字删除，直到前面的数字<=当前数字或者删除完毕。这样单调队列就派上用场了。

Accepted 3183 15MS 1404K 1003 B G++

代码如下：

#include<cstdio>//hdu3183 单调队列

#include<cstring>

#include<algorithm>

#define MAX(a,b) (a>b?a:b)

#define LL long long

#define mod 1000000007

using namespace std;

char q[1005];

int main()

{

    int n,m;

    char a[1005];

    while(~scanf("%s%d",a,&m))

    {

        n = strlen(a);

        if(n<=m)

        {

            puts("0");

            continue;

        }

        int rear = 0, cnt = 0;

        int i;

        for(i = 0; i<n; i++)

        {

            while(rear>0 && cnt<m && a[i]<q[rear])

                rear--, cnt++;

            if(cnt==m) break;

            q[++rear] = a[i];

        }

        while(rear>0 && cnt<m)//没有删除够，继续删

            rear--, cnt++;

        while(rear>0)//将队列里的元素倒入数组中，准备输出

            a[--i] = q[rear--];

        while(i<=n-2 && a[i]=='0') i++;//跳过前导0；但要留最后一位，因为答案可能就为0

        for(;i<n; i++)

            putchar(a[i]);

        putchar('\n');

    }

    return 0;

}

方法二：RMQ or 线段树

问题可以转化为：在这n个数字中选n-m个数（只能从左往右一次选），使得组成的数最小。

可知第一个数字必定在0~n-1-（m-1），即0~n-m之内取得，且取最小的数字。设第一个数取得的位置为pos，则取得第二个数的范围为：pos+1~n-m+1， 然后又将pos设为取得第二个数的位置，则取得第三个数的范围为：pos+1~n-m+2 …………

查询区间最小值可以用RMQ或者线段树实现。

RMQ：

#include<cstdio>//hdu3183 RMQ

#include<cstring>

#include<algorithm>

#include<cmath>

#define MIN(a,b) (a<b?a:b)

#define LL long long

#define mod 1000000007

using namespace std;

char s[1005], ans[1005];

int n,m,st[1005][20];//st存最值得下标

int Get_min(int x, int y)

{

    return (s[x]<=s[y]?x:y);

}

int init_RMQ()

{

    for(int i = 0; i<n; i++)

        st[i][0] = i;

    for(int j = 1; (1<<j)<n; j++)

    for(int i = 0; i+(1<<j)-1<n; i++)

        st[i][j] = Get_min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

}

int find_k(int le, int ri)

{

    int k = log(ri-le+1)/log(2);

    return Get_min(st[le][k],st[ri-(1<<k)+1][k]);

}

int main()

{

    while(~scanf("%s%d",s,&m))

    {

        n = strlen(s);

        m = n-m;

        init_RMQ();

        int pos = 0,cnt = 0;

        while(m)

        {

            pos = find_k(pos,n-m);

            ans[cnt++] = s[pos++];

            m--;

        }

        int i = 0;

        for(; i<cnt-1; i++)

            if(ans[i]!='0') break;

        if(cnt==0)

            putchar('0');

        else for(; i<cnt; i++)

            putchar(ans[i]);

        putchar('\n');

    }

    return 0;

}

线段树：

注意：在建树时，下标为mid的元素要归到左边去。

如果归到右边：

设le=3，ri=4；

mid = （le+ri）/2 = 3；

build（le，mid-1）； //实际为： build（3,2） 出错

build（mid，ri）；//实际为：build（3,4），即又为原始的le和ri， 永久执行下去……

代码如下：

#include<cstdio>//hdu3183 线段树

#include<cstring>

#include<cmath>

#include<algorithm>

#define LL long long

using namespace std;

int n,m;

char s[1005], ans[1005];

struct node

{

    int pos,le,ri;

}tree[4005];

void build(int u, int le ,int ri)

{

    tree[u].le = le;//将结点所指向的范围保存到结点中

    tree[u].ri = ri;

    if(le==ri)

    {

        tree[u].pos = le;

        return;

    }

    int mid = (le+ri)/2;

    build(u*2,le,mid);//左右建树

    build(u*2+1,mid+1,ri);

    if(s[tree[u*2].pos]<=s[tree[u*2+1].pos])

        tree[u].pos = tree[u*2].pos;

    else

        tree[u].pos = tree[u*2+1].pos;

}

int query(int u,int x, int y)

{

    int le = tree[u].le, ri = tree[u].ri;

    if(le==x && ri==y)

        return tree[u].pos;

    int mid = (le+ri)/2;

    if(y<=mid) return query(u*2,x,y);//查询范围在左边

    else if(x>mid) return query(u*2+1,x,y);//查询范围在右边

    //else return (s[query(u*2,x,mid)]<=s[query(u*2+1,mid+1,y)]?tree[u*2].pos:tree[u*2+1].pos); //有误

    else//查询范围被分成两段

    {

        int xx = query(u*2,x,mid);

        int yy = query(u*2+1,mid+1,y);

        if(s[xx]<=s[yy]) return xx;

        return yy;

    }

}

int main()

{

    while(~scanf("%s%d",s,&m))

    {

        n = strlen(s);

        m = n-m;

        build(1,0,n-1);

        int pos = 0,cnt = 0;

        while(m)

        {

            pos = query(1,pos,n-m);

            ans[cnt++] = s[pos++];

            m--;

        }

        int i = 0;

        for(; i<cnt-1; i++)

            if(ans[i]!='0') break;

        if(cnt==0)

            putchar('0');

        else for(; i<cnt; i++)

            putchar(ans[i]);

        putchar('\n');

    }

    return 0;

}

相关文章