Codeforces Round 861 (Div. 2) - C. Unlucky Numbers

Solost

2023 年 03 月 31 日

179 次浏览

暂无评论

2474字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F31%2Fimage.png)

## 题目链接

[链接](https://codeforces.com/contest/1808/problem/C)

## 题目大意

给你一个区间`L, R`问你这个区间内最不幸运的数是多少，答案可能有多个，最不幸运的定义是一个数里面最大位减去最小位差值最小。

## 题解

这个题刚开始想着dfs搜索，分两种情况。

* 位数不同
  位数不同直接遍历
* 位数相同
  如果这一位相同，就往下找，如果不同，分为上边界下边界和中间

最后优化了一下如果把后面的全部改成和当前遍历的数字相同，然后再找最小，由于搜索的时候不知道最小值是多少，反而写出来和暴力的没啥区别。

看了看别人的思路，自己重新写了一下。其实更上面的思路差不多，就是把从后面某一位开始，把他换成一堆相同的数。然后在范围内就更新一下值。

```cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
ll l, r;
bool compare(ll x){
    if(x < l || x > r) return false;
    return true;
}

int check(ll x){
    int minn, maxx;
    maxx = minn = x % 10;
    while(x){
        int t = x % 10;
        maxx = max(maxx, t);
        minn = min(minn, t);
        x /= 10;
    }
    return maxx - minn;
}

void op(ll x, vector<int> &a){
    while(x){
        a.push_back(x % 10);
        x /= 10;
    }
}

void solve(){
    cin >> l >> r;
    vector<int> a, b;
    op(l, a), op(r, b);
    ll ans = 10, var, x = 0;
    for(int i = a.size() - 1; i >= 0; i--){//枚举从哪一位开始换值
        for(int j = 0; j < 10; j++){//枚举换哪一个值
            ll res = x;
            for(int k = i; k >= 0; k--){
                res = res * 10 + j;
            }
            if(!compare(res)) continue;//检查是不是合法
            int t = check(res);//计算幸运值
            if(t < ans){
                ans = t;
                var = res;
            }
        }
        x = x * 10 + a[i];
    }
    x = 0;
    for(int i = b.size() - 1; i >= 0; i--){
        for(int j = 0; j < 10; j++){
            ll res = x;
            for(int k = i; k >= 0; k--){
                res = res * 10 + j;
            }
            if(!compare(res)) continue;
            int t = check(res);
            if(t < ans){
                ans = t;
                var = res;
            }
        }
        x = x * 10 + b[i];
    }
    cout << var << endl;
}
int main(){
    // IOS;
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 31 日