1031-1043都是排序题，所以放在一起了
1031. 冒泡排序
改良的冒泡排序，除了题目里的a,b,c外，还需要额外维护两个变量l,r作为每次冒泡排序的左右边界
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int nums[5001];
cin >> n;
for (int i = 0; i < n;i++){
cin >> nums[i];
}
int l = 0,r = n - 1;
int a = 0,b = 0,c = 0;
int p = l;
while (l < r) {
p = l;
c++;
for (int i = l;i < r;i++){
a++;
int j = i + 1;
if (nums[i] > nums[j]) {
b++;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
p = i;
}
}
r = p;
}
printf("%d %d %d\n",a,b,c);
return 0;
}1032. 插入排序
按照网上或者PPT/书里的思路就可以，唯一的坑点是行末不能有空格，不然似乎会WA
#include <bits/stdc++.h>
using namespace std;
int nums[1005] = {0};
int n;
void printNums(void) {
for (int i = 0;i < n-1;i++) {
printf("%d ",nums[i]);
}
printf("%d\n",nums[n-1]);
}
int main() {
cin >> n;
for (int i = 0;i < n;i++) {
scanf("%d",&nums[i]);
}
for (int i = 1; i < n; i++) {
int tmp = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > tmp) {
nums[j+1] = nums[j];
j--;
}
nums[j+1] = tmp;
printNums();
}
return 0;
}1033. 选择排序
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int nums[1003] = {0};
cin >> n;
for (int i = 0;i < n;i++) {
cin >> nums[i];
}
for (int i = 0; i < n - 1; i++) {
int idx = i;
for (int j = i + 1; j < n; j++)
if (nums[j] < nums[idx])
idx = j;
int tmp = nums[i];
nums[i] = nums[idx];
nums[idx] = tmp;
for (int k = 0;k < n;k++) {
cout << nums[k];
if (k != n-1) {
cout << " ";
}
}
cout << endl;
}
return 0;
}1034. 选择排序（构造）
这题其实我也没太搞明白QAQ，按照个人理解，应该是数据全部逆序就可以了，但是实际上并不是，AC的代码是前一半一样，后一半逆序
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 101350; // 数据规模
cout << n << endl;
vector<int> a(n);
// 前 5000 个元素是连续的最大值
int maxValue = n/2;
for (int i = 0; i < n/2; ++i) {
a[i] = maxValue;
}
// 后 5000 个元素是递减的数列
for (int i = n/2; i < n; ++i) {
a[i] = maxValue - (i - n/2) - 1;
}
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
return 0;
}1035. 快速排序
递归地处理左右区间，对每个区间执行这样的操作：将第一个数作为基准值，比它小的放左边，比它大的放右边，但是实际代码不是严格的“放左放右”，具体实现过程可以参考PPT。
#include <bits/stdc++.h>
using namespace std;
void quicksort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) {
cout << " ";
}
}
cout << endl;
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
quicksort(arr, 0, n - 1);
return 0;
}1036. 快速排序的优化
纯粹是按照要求进行了模拟
#include <bits/stdc++.h>
using namespace std;
void Selectsort(vector<int>& nums, int left, int right) {
for (int i = left; i < right; i++) {
int idx = i;
for (int j = i + 1; j <= right; j++) {
if (nums[j] < nums[idx]) {
idx = j;
}
}
int tmp = nums[i];
nums[i] = nums[idx];
nums[idx] = tmp;
}
}
int find(vector<int>& arr,int left,int right) {
int mid = (left + right) >> 1;
if (arr[left] > arr[mid]) swap(arr[left], arr[mid]);
if (arr[left] > arr[right]) swap(arr[left], arr[right]);
if (arr[mid] > arr[right]) swap(arr[mid], arr[right]);
return mid;
}
void quicksort(vector<int>& arr, int left, int right) {
if (left >= right) return;
if (right - left + 1 <= 100) {
Selectsort(arr,left,right);
return;
}
int pi = find(arr,left,right);
swap(arr[left],arr[pi]);
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (n <= 100) {
Selectsort(arr, 0, n-1);
}else {
quicksort(arr, 0, n - 1);
}
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) {
cout << " ";
}
}
cout << endl;
return 0;
}1037. 鞍点
最好写，不用动脑子的做法：直接一个二维矩阵存图，对于每个元素跑一次check函数（遍历该元素所在行、列，确认这个元素是否为最小的），如果是，把这个元素的坐标放进答案（我用了c++的pair和vector），最后把答案排序输出即可
#include <bits/stdc++.h>
using namespace std;
int arr[6][6];
bool check(int x,int y) {
for (int i = 0;i < 5;i++) {
if (arr[i][y] < arr[x][y]) return false;
}
for (int j = 0;j < 5;j++) {
if (arr[x][j] > arr[x][y]) return false;
}
return true;
}
int main() {
int t;
cin >> t;
for(int cas = 0;cas < t;cas++) {
printf("case #%d:\n",cas);
bool flag = false;
vector<pair<int,int>> res;
for (int i = 0;i < 5;i++) {
for (int j = 0;j < 5;j++) {
cin >> arr[i][j];
}
}
for (int i = 0;i < 5;i++) {
for (int j = 0;j < 5;j++) {
if (check(i,j)) {
flag = true;
res.push_back(make_pair(i,j));
}
}
}
sort(res.begin(),res.end());
if (!flag) {
cout << -1 << " " << -1 << endl;
} else {
for (auto& p:res) {
cout << p.first << " " << p.second << endl;
}
}
}
return 0;
} 1038. 统计工龄
由于工龄的范围很小（0~50），所以用一个数组cnt，cnt[i]表示工龄为i的老师数量即可
#include <bits/stdc++.h>
using namespace std;
int cnt[51] = {0};
int main() {
int n,year;
cin >> n;
for (int i = 0;i < n;i++) {
cin >> year;
cnt[year]++;
}
for (int i = 0;i <= 50;i++) {
if (cnt[i] != 0) {
printf("%d:%d\n",i,cnt[i]);
}
}
return 0;
}1039. 排名汇总
感觉回到了C语言临近期末天天写结构体排序的日子。。
这种题一般就是这个步骤：
- 声明一个结构体（比如学生），把各种属性（学号，年龄，成绩之类）都放进去
- 声明一个结构体数组
- 写一个自定义比较函数
- 最后排序结构体数组
这道题比较烦的是又要某学生在自己考场里的排名，又要总学生里的排名，我当时的处理方法是给学生结构体设了一个变量rk表示他在自己考场内的排名，通过每次读取完一个考场的学生信息后排序得到；
总排名则是将所有学生都放在一个数组里，再进行一次排序得到
#include <bits/stdc++.h>
using namespace std;
int n,t;
int num = 0;
struct student {
string id;
int score;
int pos;
int rk; //这个学生在自己考场里的排名
};
vector<student> all_students;
bool cmp(const student& stu1,const student& stu2) {
if (stu1.score != stu2.score) return stu1.score > stu2.score;
return stu1.id < stu2.id;
}
void solve() { //每读取一个考场，就对这个考场内部进行排名，得到学生的rk
int k;
cin >> k;
num += k;
// cout << "pp" << t<<endl;
vector<student> students;
for (int i = 0;i < k;i++) {
student stu;
cin >> stu.id >> stu.score;
stu.pos = t;
students.push_back(stu);
}
sort(students.begin(),students.end(),cmp);
int rank = 1;
int cnt = 0;
int prescore = 0;
for (int i = 0;i < k;i++) {
cnt++;
// cout << "here" << endl;
if (students[i].score != prescore) {
rank = cnt;
}
students[i].rk = rank;
prescore = students[i].score;
all_students.push_back(students[i]);
}
}
int main() {
cin >> n;
// vector<student> all_students;
for (t = 1;t <= n;t++) {
solve(); //每读取一个考场，就对这个考场内部进行排名，得到学生的rk
}
sort(all_students.begin(),all_students.end(),cmp);
int prescore = 0;
int rank = 0;
cout << num << endl;
int cnt = 0;
for (int i = 0;i < num;i++) {
cnt++;
if (all_students[i].score != prescore) {
rank = cnt;
}
prescore = all_students[i].score;
cout << all_students[i].id << " " << rank << " " << all_students[i].pos << " " << all_students[i].rk << endl;
}
return 0;
}1042. 二维数组排序
经典C语言排序重出江湖，如果忘了怎么写可以翻翻C语言教材
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 100
#define N 100
//********** Specification of SortLines **********
int col;
int cmp(const void* a, const void* b) {
int* row1 = (int*)a;
int* row2 = (int*)b;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < col; i++) {
sum1 += row1[i];
sum2 += row2[i];
}
if (sum1 != sum2) {
return sum1 - sum2;
}
for (int i = 0; i < col; i++) {
if (row1[i] != row2[i]) {
return row1[i] - row2[i];
}
}
return 0;
}
void SortLines(int (*p)[M], int n, int m) {
col = m;
qsort(p, n, sizeof(p[0]), cmp);
}
/***************************************************************/
int main() {
int a[N][M];
int n,m,i,j;
int t,cas;
scanf("%d",&cas);
for(t=0; t<cas; t++) {
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for (i=0; i<n; i++)
for (j=0; j<m; j++)
scanf("%d",&a[i][j]);
/***** function SortLines is called here *****/
SortLines(a,n,m);
/****************************************/
printf("case #%d:\n",t);
for (i=0; i<n; i++)
for (j=0; j<m; j++)
printf("%d%c",a[i][j],j<m-1?' ':'\n');
}
return 0;
}1043. 寻找EMB富豪
省流：相信库函数的实力（不是）
直接调库就能过，我当时就没继续研究，另外附上一位网络大佬的做法，使用了堆排序：https://blog.csdn.net/rd142857/article/details/121778442
#include <bits/stdc++.h>
using namespace std;
// int Rand(int i){
// return rand() % i;
// }
inline int read() { //优化读入速度，但其实不加差不多也能过
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
x = x*10 + ch -'0',ch = getchar();
return x*f;
}
bool cmp(const int& a,const int& b) {
return a > b;
}
int main() {
int n,m;
cin >> n >> m;
int nums[n];
for (int i = 0;i < n;i++) {
nums[i] = read();
}
// random_shuffle(nums,nums+n);
sort(nums,nums+n,cmp);
m = min(n,m);
for (int i = 0;i < m;i++) {
printf("%d ",nums[i]);
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
int a[200001] = { 0 };
void siftdown(int a[], int i, int n)
// 调整以a[i]为根的二叉树使之成为小根堆
// 每次替换走堆顶的最小元素，保证新加入的元素为更大的元素
// 若建立大根堆，不可以替换走堆顶（最大），替换走最小元素更麻烦
{
int j;
int tmp = a[i];
while ((j=2*i+1)<n)
{
if (j < n - 1 && a[j + 1] < a[j])
j++;
if (tmp > a[j]) // 需要调整
{
a[i] = a[j];
i = j;
}
else break;
}
a[i] = tmp;
}
void buildHeap(int a[], int n)
{
for (int i = (n - 2) / 2; i >= 0; i--)
siftdown(a, i, n);
}
void heapSort(int a[], int n)
// a已经是小根堆，排序结束后变成大根堆
{
if (n == 0)
return;
// buildHeap(a, n);
for (int i = n - 1; i >= 1; i--)
{
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
siftdown(a, 0, i);
}
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
int val;
scanf("%d", &val);
if (i < m)
a[i] = val;
else
{
if(i==m)
buildHeap(a, m);
// 如果val大于堆顶，则需要加入
if (a[0] < val)
{
a[0] = val;
siftdown(a, 0, m);
}
}
}
if (n <= m) // 此时数组并未经过排序
{
buildHeap(a, n);
heapSort(a, n);
for (int i = 0; i < n; i++)
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
else
{
heapSort(a, m);
for (int i = 0; i < m; i++)
printf("%d%c", a[i], i == m - 1 ? '\n' : ' ');
}
return 0;
}