M_sea

CF435B Pasha Maximizes
CodeforcesLuogu分析人生第一道灰题。从最后结果最大的角度出发,从高到低考虑每一位,在能够变到该位的所...
扫描右侧二维码阅读全文
03
2018/11

CF435B Pasha Maximizes

Codeforces

Luogu

分析

人生第一道灰题。

从最后结果最大的角度出发,从高到低考虑每一位,在能够变到该位的所有位中选择一个最大的变过来。

举个例子:

1423 2

$4$和$2$都可以变到$1$这里来。选择一个最大的变过来,就变成了$4123$。

当然现在只转了一次,还可以转一次。

那么考虑第二位$1$,此时只有$2$可以变过来。所以最后产生的最大的数就是$4213$。

大致思路就是这样,时间复杂度为$O(n^2)$,$n$是数的长度

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

char tmp[100000];
int a[100000];

inline int min_(int a,int b) { return a<b?a:b; }
inline void swap_(int& a,int& b) { re int c=a; a=b,b=c; }

int main() {
    char c=getchar(); int n=0;
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') a[++n]=c-'0',c=getchar();
    re int k; scanf("%d",&k);
    for (re int i=1;i<=n;++i) {
        int pos=i;
        int E=min_(i+k,n);
        for (re int j=i+1;j<=E;++j)
        if (a[j]>a[pos]) pos=j;
        if (pos==i) continue;
        for (re int j=pos;j>i;--j)
        swap_(a[j],a[j-1]);
        k-=(pos-i); if (k==0) break;
    }
    for (re int i=1;i<=n;++i) putchar(a[i]+'0'); putchar('\n');
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 52 PM

发表评论