周赛40

依旧是掉大分的一天…

斐波那契字符串

题目链接：https://www.acwing.com/problem/content/4308/

注意边界条件是f[i - 1] <= n而不是i < n要不然就Segmentation Fault

序列处理

题目链接：https://www.acwing.com/problem/content/4309/
贪心题
第一个数取本身，当前数取max(自身，前一个数+1）

证明：
变换过程是 a——>a’ ， b——>b’ （原a < b）
证其保序性（即a’ < b’）

1. 假设变换后a’ > b’，则此时变换的代价为 a’ - a + b’ - b，
2. 又因为b’ >= b > a，a’ > b’ >= b，所以变换也可以这么做：a——>b’ ， b——>a’ ，而此时的代价为 b’ - a + a’ - b，代价不变。
3. 所以我们可以把 a’ 和 b’ 交换，这样就实现了（现）a’ < b’，即维持了他的保序性

（不能个上传图片真的说起来好费劲啊emmm

相似题：能量石https://www.acwing.com/problem/content/736/

数字重构

题目链接：https://www.acwing.com/problem/content/4310/
又是贪心！
从高位开始，从9到1枚举一下
当前位可取数字 i 的条件：

1. 有数字 i （可选）

2. $$ 后面存在一种摆法，使得 a <= b，\\也就是最小摆法a_{min} <= b $$

所以就把当前位置后面的的位数升序排列就好了

get新用法：
to_string()：将数值转化为字符串。返回对应的字符串。

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;
string a, b, res;
int c[20], n, cnt[10];

string find (int x){
    string res = to_string(x);
    cnt[x] --;

    for (int i = 0; i <= 9; i ++)
        for (int j = 0; j < cnt[i]; j ++)
            res += to_string(i);

    cnt[x] ++;
    return res;
}

int main(){
    cin >> a >> b;
    n = a.size();

    if (n < b.size()){
        sort (a.begin(), a.end(), greater<char>());
        cout << a << endl;
    }

    else{
        for (auto c : a)
            cnt[c - '0'] ++;//表示这个数存在于a中


    for (int i = 0; i < n; i ++)
        for (int j = 9; j >= 0; j --){
            if (cnt[j] && res + find(j) <= b){//有此i并且a <= b
                res += to_string(j);
                cnt[j] --;
                break;
            }

        }

    }

    cout << res;
    return 0;
}