题目描述及样例
详见:
https://www.acwing.com/problem/content/4656/
思路:后放入的一定在同一数值类的后面加入
我们用map<int, vector<int>>
来存储数位和为first的一堆数;
简单试几个就知道有上述规律:
1 10 2 11 20 3 12 21 4 13 22 5 14 6 15 7 16 8 17 9 18 19
求数位和我们用了一个很直观的方法,就是转成string逐位判断,
因为不用考虑权值,所以这种方法很简单;
时间复杂度O(nlogn)
1e6的数据,首先想到O(n)和O(nlogn),
鉴于map的操作是O(logn)的,于是我在做的时候猜想这样可以过;
C++ 代码
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
using namespace std;
#define endl "\n"
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fir first
#define sec second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
#define ORZ cout << "Orz" << endl;
int rnd(int x) { return mrand() % x;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int n, m;
map <int, vector<int>> mm;
inline int numSum(int x){
int val = 0;
string str = to_string(x);
int len = str.size();
per(i, len - 1, 0){
int tmp;
tmp = int(str[i] - '0');
val += tmp;
}
return val;
}
int main(){
ios;
cin >> n >> m;
rep(i, 1, n){
mm[numSum(i)].push_back(i);
}
for (auto i : mm){
for (auto j : i.sec){
m--;
if (m == 0){
cout << j << endl;
return 0;
}
}
}
return 0;
}
喜欢的话不妨表示一下~