观前提示：本文部分内容由AI生成

拼数

简化版题意

给定一个长度小于等于$10^6$ ，仅包含小写英文字母及数字的字符串 $s$，可以使用 $s$ 中的任意多个数字，按任意顺序拼成一个正整数。求能拼出的最大正整数。($s$中保证至少有一个$1$~$9$的数字)

法一:直接排序

• 从字符串中提取所有数字字符，存入容器（如 vector）
• 对数字字符按字典序从小到大排序，再反转得到从大到小的顺序
• 依次输出排序后的字符，即为最大正整数

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    vector<char> a;
    for(int i=0;i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9')
            a.push_back(s[i]);
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();i++){
        cout<<a[i];
    }
    return 0;
}

法二：计数排序法

核心思路

1. 用一个大小为 10 的数组统计 0-9 每个数字出现的次数
2. 从 9 到 0 依次输出对应次数的数字，直接得到降序排列的最大数

优势

相比法一，时间复杂度更低$(O(n))$，$n$为字符串长度），适合处理大输入（如$10^6$长度的字符串）

代码：

#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9')
        a[s[i]-'0']++;
    }
    for(int i=9;i>=0;i--){
        if(a[i]!=0)while(a[i]--)cout<<i;
    }
    return 0;
}

法三：优先队列法

• 利用优先队列（大根堆）的特性，自动维护元素的降序排列
• 将所有数字字符入队，再依次出队拼接，得到最大正整数

代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    priority_queue<char> pq; 
    // 数字入堆（O(m log m)时间）
    for (int i=0;i<s.size();i++) {
        char c=s[i];
        if (isdigit(c)) {
            pq.push(c);
        }
    }
    // 出堆拼接（O(m log m)时间）
    string res;
    while (!pq.empty()) {
        res += pq.top();
        pq.pop();
    }
    cout << res << endl;
    return 0;
}

座位

简化版题意

将$m\times n$个考生的成绩按从高到低的顺序，以 “蛇形” 方式排列（第$1$ 列从上到下，第 $2$ 列从下到上，第 $3$ 列从上到下… 以此类推）。要求找出原始输入序列中第一个人的成绩在蛇形排列中的坐标（列号在前，行号在后）。

思路：模拟蛇形排列过程

1. 先提取原始序列的第一个成绩（记为$t$）
2. 将所有成绩按从高到低排序
3. 模拟蛇形填充过程：
   • 从第 1 行第 1 列开始填充
   • 奇数列（第 1、3、5… 列）：从上到下填充，填满后列号 + 1
   • 偶数列（第 2、4、6… 列）：从下到上填充，填满后列号 + 1
4. 找到成绩t在蛇形排列中的位置，输出其列号和行号

关键移动规则

• 若在奇数行第 1 列 或 偶数行第 n 列：列号 + 1（切换到下一列）
• 若在奇数列（且不在边界）：行号 + 1（向下移动）
• 若在偶数列（且不在边界）：行号 - 1（向上移动）

代码：

#include<bits/stdc++.h>
using namespace std;
int q[15][15];
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a;
for(int i=0;i<n*m;i++){
    int t;
    cin>>t;
    a.push_back(t);
}
    int t=a[0];
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    int i=1,j=1;
for(int k=0;k<n*m;k++){
    q[i][j]=a[k];
    if(i==1&&j%2==0)j++;
    else if(i==n&&j%2==1)j++;
    else if(j%2==1){
        i++;
    }else{
        i--;
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(q[i][j]==t){
            cout<<j<<" "<<i;
            return 0;
        }
    }
}
    return 0;
}