题目链接
题目大意
给你一个区间L, R
问你这个区间内最不幸运的数是多少,答案可能有多个,最不幸运的定义是一个数里面最大位减去最小位差值最小。
题解
这个题刚开始想着dfs搜索,分两种情况。
- 位数不同
位数不同直接遍历 - 位数相同
如果这一位相同,就往下找,如果不同,分为上边界下边界和中间
最后优化了一下如果把后面的全部改成和当前遍历的数字相同,然后再找最小,由于搜索的时候不知道最小值是多少,反而写出来和暴力的没啥区别。
看了看别人的思路,自己重新写了一下。其实更上面的思路差不多,就是把从后面某一位开始,把他换成一堆相同的数。然后在范围内就更新一下值。
#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;
}