【每日一题丨2025年5.12～5.18】排序相关题

发布于：2025-05-20 ⋅ 阅读:(20) ⋅ 点赞:(0)

在这里插入图片描述

个人主页：Guiat
归属专栏：每日一题

在这里插入图片描述

文章目录

正文

1. 【5.12】P1068 [NOIP 2009 普及组] 分数线划定

题目链接：https://www.luogu.com.cn/problem/P1068

【分析】
模拟排序题，复杂一点的是处理排序后的选手，按照要求输出答案。

【AC_Code】

#include <iostream>
#include <algorithm>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

struct str { int n, s; } p[5010]; int cnt;

bool cmp(str x, str y)
{
    if (x.s == y.s) return x.n < y.n;
    return x.s > y.s;
}

void solve()
{
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i ++) { cin >> p[i].n >> p[i].s; }
    sort(p, p + n, cmp);
    int S = floor(m * 1.5);
    int score_line = p[S-1].s;  // 分数线是第S个人的分数
    for (int i = 0; i < n; i ++)
    {
        if (p[i].s >= score_line) cnt ++; else break;
    }
    cout << score_line << ' ' << cnt << '\n';
    for (int i = 0; i < cnt; i ++) cout << p[i].n << ' ' << p[i].s << '\n';
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

2. 【5.13】P5143 攀爬者

题目链接：https://www.luogu.com.cn/problem/P5143

【分析】

简单模拟排序题，这类题往往需要写一个结构体数组和一个比较函数，剩下的只需按题意模拟即可。

【AC_Code】

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fix(x) setprecision(x) << fixed

using namespace std;

struct str{ int x, y, z; } s[50010]; double ans;

bool cmp(str a, str b) { return a.z < b.z; }

void solve()
{
    int n; cin >> n;
	for (int i = 0; i < n; i ++) cin >> s[i].x >> s[i].y >> s[i].z;
	sort(s, s + n, cmp);
	for (int i = 0; i < n - 1; i ++)
	{
		ans += sqrt(pow(s[i].x - s[i + 1].x, 2) + pow(s[i].y - s[i + 1].y, 2) + pow(s[i].z - s[i + 1].z, 2));
	}
	cout << fix(3) << ans << '\n';
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

3. 【5.14】P12366 [蓝桥杯 2022 省 Python B] 数位排序

题目链接：https://www.luogu.com.cn/problem/P12366

【分析】
无需用到结构体。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e6 + 10; int a[N], ans;

int getSum(int num)
{
	int sum = 0;
	while (num) { sum += num % 10; num /= 10; }
	return sum;
}

bool cmp(int a, int b)
{
	if (getSum(a) < getSum(b)) return true;
	if (getSum(a) == getSum(b) && a < b) return true;
	return false;
}

void solve()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) { a[i] = i; }
    sort(a + 1, a + 1 + n, cmp);
	cout << a[m] << '\n';
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

4. 【5.15】P10901 [蓝桥杯 2024 省 C] 封闭图形个数

题目链接：https://www.luogu.com.cn/problem/P10901

【分析】
构建一个封闭图形个数数组，发现下标刚好是要处理的单个数字，后面就很好写了。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5 + 10; int a[N], num[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 };

int cnt(int NUM)
{
	int CNT = 0;
	while (NUM) { CNT += num[NUM % 10]; NUM /= 10; }
	return CNT;
}

bool cmp(int a, int b)
{
	if (cnt(a) < cnt(b)) return true;
	if (cnt(a) == cnt(b) && a < b) return true;
	return false;
}

void solve()
{
    int n; cin >> n; for (int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i ++) cout << a[i] << " \n"[i == n - 1];
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

5.【5.16】P12165 [蓝桥杯 2025 省 C/Java A] 最短距离

题目链接：https://www.luogu.com.cn/problem/P12165

【分析】
考察最朴素的贪心，可以用数学归纳法证明，比较高大上，这里不再赘述，可自行AI，最简单实用的可以通过举反例证明其合理性。

【AC_Code】

#include <iostream>
#include <algorithm>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;

const int N = 5e4 + 10; int a[N], b[N]; ll ans;

void solve()
{
    int n; cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n; i ++) cin >> b[i];
    sort(a, a + n); sort(b, b + n);
    for (int i = 0; i < n; i ++) ans += abs(a[i] - b[i]);
    cout << ans << '\n';
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

6. 【5.17】P12186 [蓝桥杯 2025 省 Python A/研究生组] 最大数字

题目链接：https://www.luogu.com.cn/problem/P12186

【分析】
这题还没理解，参考题解代码。

【AC_Code】

#include <bits/stdc++.h>
using namespace std;
using ull = int;

// 表示大整数的结构体，使用向量存储每一位数字
struct BigInt {
    vector<ull> digits;
};

// 初始化大整数为 0
void initBigInt(BigInt& num) {
    num.digits = {0};
}

// 将大整数乘以 2
void mult2(BigInt& num) {
    ull carry = 0;
    for (int i = 0; i < num.digits.size(); ++i) {
        ull product = num.digits[i] * 2 + carry;
        num.digits[i] = product % 10;
        carry = product / 10;
    }
    if (carry != 0) {
        num.digits.push_back(carry);
    }
}

// 将大整数加 1
void add1(BigInt& num) {
    ull carry = 1;
    for (int i = 0; i < num.digits.size() && carry > 0; ++i) {
        ull sum = num.digits[i] + carry;
        num.digits[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry > 0) {
        num.digits.push_back(carry);
    }
}

// 输出大整数
void output(const BigInt& num) {
    int i = num.digits.size() - 1;
    // 跳过前导零
    while (i >= 0 && num.digits[i] == 0) {
        --i;
    }
    // 如果所有位都是零，输出 0
    if (i < 0) {
        cout << "0";
        return;
    }
    // 从高位到低位输出
    while (i >= 0) {
        cout << num.digits[i];
        --i;
    }
}

// 将数字向量转换为二进制字符串
string toBinaryString(const vector<ull>& nums) {
    string bs;
    for (ull num : nums) {
        if (num == 0) {
            bs += "0";
        } else {
            string temp;
            while (num > 0) {
                temp = (num % 2 == 0 ? "0" : "1") + temp;
                num /= 2;
            }
            bs += temp;
        }
    }
    return bs;
}

// 将二进制字符串转换为大整数
BigInt trans(const vector<ull>& nums) {
    string bs = toBinaryString(nums);
    BigInt res;
    initBigInt(res);
    for (char bit : bs) {
        mult2(res);
        if (bit == '1') {
            add1(res);
        }
    }
    return res;
}

int main() {
    ull x;
    cin >> x;
    vector<ull> nums(x);
    for (int i = 0; i < x; i++) {
        nums[i] = i + 1;
    }
    // 自定义排序
    sort(nums.begin(), nums.end(), [](ull a, ull b) {
        ull bitA = log2(a) + 1;
        ull bitB = log2(b) + 1;
        ull tempA = (a << bitB) + b;
        ull tempB = (b << bitA) + a;
        return tempA > tempB;
    });
    
    BigInt bs = trans(nums);
    output(bs);
    
    return 0;
}

7. 【5.18】P1012 [NOIP 1998 提高组] 拼数

题目链接：https://www.luogu.com.cn/problem/P1012

【分析】
这题凭感觉写的，发现自己还不会证明QAQ。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

string s[25];

bool cmp(string a, string b) { return a + b > b + a; }

void solve()
{
	int n; cin >> n;
	for (int i = 0; i < n; i ++) cin >> s[i];
	sort(s, s + n, cmp);
	for (int i = 0; i < n; i ++) cout << s[i]; cout << '\n'; 
}

int main()
{
    IOS int _ = 1;   // cin >> _;
    while (_ --) solve();
    
    return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布