- 题目来源：ZOJ Problem Set -- 4085 Little Sub and Mr.Potato's Math Problem
题意：Q(n，k)=m
将n个数按照字典序排序，k所在的位置为m
现在给出k，m 求最小的n
思路：
当k为10的整数倍，那么它一定在第 log以10为底k 的位置上
随后统计当n==k的时候，排在k前面的个数，和m比较，判断是否合法
接着不断增加n，统计每次增长排在k前面的个数，随后输出n
自己的代码;
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#include <ctime>
using namespace std;
#define ll long long
const int maxn = 1e5 + 100;
const ll mod = 1e9 + 7;
ll p[18];
void init()
{p[0] = 0;p[1] = 10;for (int i = 2;i <= 17;i++){p[i] =p[i-1] * 10;}
}
int go(int x)
{int cnt = 0;while (x){x /= 10;cnt++;}return cnt;
}
ll f(ll x)
{int cnt = go(x);if (cnt == 1){return x - p[cnt - 1] - 1;}ll sum_ = x-p[cnt-1];//cout << sum_ << endl;;for (int i = 1;i < cnt;i++){ll sum = x / p[i];//cout <<sum<<" ** "<< sum - p[cnt - i - 1]+1 << endl;if (i == cnt - 1){sum_ += sum - p[cnt - i - 1] ;}else{sum_ += sum - p[cnt - i - 1] + 1;}//cout << cnt - i << " " << sum_ << endl;}return sum_;
}ll ff(ll x,int m)
{int cnt = go(x);ll sum=x;ll sum_ = 0;for (int i = cnt;;i++){sum = sum * 10;sum_ = sum - p[i];//cout << sum_ << " "<<m<<endl;if (sum_ <= m){m -= sum_;}else{return p[i] + m-1;}}
}
int main()
{int T;cin >> T;init();while (T--) {ll k, m;scanf("%lld%lld", &k, &m);//cout << f(k) << endl;m = m - f(k) - 1;if (m < 0){cout << 0 << endl;continue;}if (m == 0){cout << k << endl;continue;}cout << ff(k, m) << endl;}system("pause");return 0;
}
/*1
3 5
1 2 3
1
0 0 3
1
0 2 1
1
*/
大佬的代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long long ull;const double eps = 1e-8;
const ll MOD = 1e9 + 7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;ll k, m;
int arr[maxn];
ll pow_10[10];void Init()
{pow_10[0] = 1;for (int i = 1; i <= 18; ++i){pow_10[i] = pow_10[i - 1] * 10;}
}void solve()
{ll num = 1;for (int i = 1;; ++i){if (num > k) break;else if (num == k){if (i == m){printf("%lld\n", k);return;}else{puts("0");return;}}num *= 10;}int len = 0;num = k;while (num){arr[++len] = num % 10;num /= 10;}reverse(arr + 1, arr + 1 + len);ll ans = 0;num = 0;for (int i = 1; i <= len; ++i){num = num * 10 + arr[i];ans += num - pow_10[i - 1];if (i != len) ++ans;}if (ans >= m){puts("0");return;}else if (ans == m - 1){printf("%lld\n", k);return;}while (1){len++;num *= 10;if (ans + num - pow_10[len - 1] >= m - 1){ans = pow_10[len - 1] + m - ans - 2;printf("%lld\n", ans);return;}ans += num - pow_10[len - 1];}
}void RUN()
{Init();int t;scanf("%d", &t);while (t--){scanf("%lld %lld", &k, &m);solve();}
}int main()
{
#ifdef LOCAL_JUDGEfreopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGERUN();#ifdef LOCAL_JUDGEfclose(stdin);
#endif // LOCAL_JUDGEreturn 0;
}