AcWing 4653. 数位排序【全程注释解析,能看懂就真的理解了!】
原题链接
简单
作者:
MQy
,
2023-01-03 21:34:02
,
所有人可见
,
阅读 288
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N];
// 此题非常的简单,如果看过 y总 的基础课 第一节,
// 就知道这题考的是原题!只是 排序的规则变化了。需要我们自己手写一下!
// 手写的排序规则,只要写出来是那个意思就行。也不需要管那么多。先 AC 再说!
bool compareAB(int a, int b) {
// 先拷贝下,一会儿取每位数用tenmpA和tempB,因为若 数位和不相等,还得比较 a 和 b 呢。
int tempA = a, tempB = b;
// 所以 a 和 b 不能改动!
int sumA = 0, sumB = 0;
// 求数位和
do {
sumA += tempA % 10;
} while ((tempA /= 10) != 0);
do {
sumB += tempB % 10;
} while ((tempB /= 10) != 0);
// 比较的逻辑
if (sumB != sumA) {
return sumA > sumB;
}
else {
return a > b;
}
}
// 快速选择模板,或者叫 快速排序模板的变形
int quick_select(int l, int r, int m) {
while (l >= r) return q[r];
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (compareAB(x, q[i]));
do j--; while (compareAB(q[j], x));
if (i < j) swap(q[i], q[j]);
}
// 判断下当前 第 m 个 是否在左区域
if (j - l + 1 >= m) {
quick_select(l, j, m); // 若在左区域,那么就只需要把做区域排序即可
}
else {// 若在右区域,那么只需要 k - 左区域的元素数量,就知道第 k 个数,在右区域是 第 几个了!
// 然后 只要把 右区域进行排序即可!
quick_select(j + 1, r, m - (j - l + 1));
}
}
int main(void) {
int n, m;
cin >> n >> m;
for (int i = 0, j = 1; i < n; ++i) {
q[i] = j++;
}
int ret = quick_select(0, n - 1, m);
cout << ret << endl;
return 0;
}
为什么这道题换成 j >= m 和 quick_select(j + 1, r, m); 也能过,很困惑这个点,求大佬解释
测试样例的问题吧?
但是AC了
啊不对,y总讲的就是我说的那个,你这个和y总的不一样,这道题这两种都能AC,我不理解,应该是不同的吧