7-1 统计工龄

给定公司 n 名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。

输入格式:

输入首先给出正整数 n（≤105），即员工总人数；随后给出 n 个整数，即每个员工的工龄，范围在 [0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

实现代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[55];

int main(){
	cin>>n;
	int maxn=0;
	for(int i=0;i<n;i++){
		cin>>m;
		maxn=max(m,maxn);
		a[m]++;
	}
	for(int i=0;i<=maxn;i++){
		if(a[i]>0) cout<<i<<":"<<a[i]<<endl;
	}
	return 0;
}

7-2 寻找大富翁

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

输入格式:

输入首先给出两个正整数N（≤106）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。

输出格式:

在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。

输入样例:

8 3
8 12 7 3 20 9 5 18

输出样例:

20 18 12

实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int n,k;
int main(){
    cin>>n>>k;
    if(n<=0||k<=0) return 0;
    if(k>n) k=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=n-k+1;i--){
        cout<<a[i];
        if(i!=n-k+1) cout<<" ";
    }
        return 0;
}

7-3 点赞狂魔

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：

输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F1​⋯FK​”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fi​（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。

输出格式：

统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：

5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14

输出样例：

jack chris john

实现代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    string name;
    int sum,ci;
    double ave;
}ren[105];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>ren[i].name>>ren[i].sum;
        map<int,int> mp;
        for(int j=0;j<ren[i].sum;j++){
            int x;
            cin>>x;
            mp[x]++;
        }
        ren[i].ci=mp.size();
        ren[i].ave=ren[i].sum*1.0/ren[i].ci;
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(ren[j].ci<ren[j+1].ci){
                swap(ren[j],ren[j+1]);
            }//?
            else if(ren[j].ci==ren[j+1].ci&&ren[j].ave>ren[j+1].ave){
                swap(ren[j],ren[j+1]);
            }
        }
    }
    if(n==1){
        cout<<ren[0].name<<" - -"<<endl;
    }
    else if(n==2){
        cout<<ren[0].name<<" "<<ren[1].name<<" -"<<endl;
    }
    else{
        cout<<ren[0].name<<" "<<ren[1].name<<" "<<ren[2].name<<endl;
    }
}

7-4 插入排序还是归并排序

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 n (≤100)；随后一行给出原始序列的 n 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

实现代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,pos,i,j,range=2,a[105],b[105];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
        cin>>b[i];
    for(i=1;i<n;i++)
        if(b[i]<b[i-1])break;
    for(j=i;j<n;j++)
        if (a[j] != b[j])break;
    if(j==n){
        printf("Insertion Sort\n");
        sort(b,b+i+1);
    }
    else{
        printf("Merge Sort\n");
        while (1){
            for (i=0;i<n/range;i++)
                sort(a+i*range,a+(i+1)*range);
            sort(a+i*range,a+n);
            for(i=0;i<n;i++)
                if (a[i]!=b[i])break;
            if(i==n){
                range*=2;
                for(i=0;i<n/range;i++)
                    sort(b+i*range,b+(i+1)*range);
                sort(b+i*range,b+n);
                break;
            }
            range*=2;
        }
    }
    cout<<b[0];
    for(i=1;i<n;i++)
        cout<<" "<<b[i];
}

7-5 插入排序还是堆排序

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

堆排序也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 n (≤100)；随后一行给出原始序列的 n 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出 Insertion Sort 表示插入排序、或 Heap Sort 表示堆排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

输出样例 2：

Heap Sort
5 4 3 1 0 2 6 7 8 9

实现代码：

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

struct heap
{
    vector<int> data;
    void up(int index)
    {
        while (index > 0)
        {
            int fa = (index - 1) / 2;
            if (data[fa] < data[index])
            {
                swap(data[fa], data[index]);
                index = fa;
            }
            else
            {
                break;
            }
        }
    }
    void down(int index)
    {
        int size = data.size();
        while (index < size)
        {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largest = index;
            if (leftChild < size && data[leftChild] > data[largest])
            {
                largest = leftChild;
            }
            if (rightChild < size && data[rightChild] > data[largest])
            {
                largest = rightChild;
            }
            if (largest != index)
            {
                swap(data[largest], data[index]);
                index = largest;
            }
            else
            {
                break;
            }
        }
    }
    int top()
    {
        return data.front();
    }
    int pop()
    {
        swap(data[0], data[data.size() - 1]);
        data.pop_back();
        down(0);
        return 0;
    }
    int push(int x)
    {
        data.push_back(x);
        up(data.size() - 1);
        return 0;
    }
    int at(int n)
    {
        return data[n];
    }
};
int main()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &it : a)
        cin >> it;
    for (auto &it : b)
        cin >> it;
    int tmp;
    if (b[1] < b[0])
    {
        sort(all(a));
        cout << "Heap Sort\n";
        for (int i = n - 1; i >= 0; i--)
        {
            if (b[i] != a[i])
            {
                tmp = i;
                break;
            }
        }
        heap p;
        for (int i = 0; i <= tmp; i++)
        {
            p.push(b[i]);
        }
        int l = p.top();
        p.pop();
        for (int i = 0; i < tmp; i++)
        {
            cout << p.at(i) << " ";
        }
        cout << l << " ";
        for (int i = tmp + 1; i < n - 1; i++)
        {
            cout << b[i] << " ";
        }
        cout << b[n - 1];
    }
    else
    {
        cout << "Insertion Sort\n";
        for (int i = 1; i < n; i++)
        {
            int j = i;
            while (a[j] < a[j - 1] && j > 0)
            {
                swap(a[j], a[j - 1]);
                j--;
            }
            if (a == b)
            {
                tmp = i;
                break;
            }
        }
        tmp++;
        while (a[tmp] < a[tmp - 1])
        {
            swap(a[tmp], a[tmp - 1]);
            tmp--;
        }
        for (int i = 0; i < n - 1; i++)
        {
            cout << a[i] << " ";
        }
        cout << a[n - 1];
    }
    return 0;
}

7-6 链式基数排序

实现链式基数排序，待排序关键字n满足1≤n≤1000，最大关键字数位≤5。

输入样例：

第一行输入待排序个数n（1≤n≤1000）,再输入n个数(n的数位≤5)。

10
278 109 63 930 589 184 505 269 8 83

输出样例：

输出每趟分配-收集后链表中的关键字，趟数为序列中最大值的数位（如样例中930的数位为3），每行结尾有空格。

930 63 83 184 505 278 8 109 589 269 
505 8 109 930 63 269 278 83 184 589 
8 63 83 109 184 269 278 505 589 930 

实现代码：

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
int solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> tmp(10);
    for (auto &it : a)
        cin >> it;
    int maxx = *max_element(all(a));
    int m = 0;
    while (maxx)
    {
        ++m;
        maxx /= 10;
    }
    int q = 1;
    while (m--)
    {
        tmp.clear();
        tmp.resize(10);
        for (int i = 0; i < n; i++)
        {
            tmp[(a[i] / q % 10)].emplace_back(a[i]);
        }
        a.clear();
        for (int i = 0; i < 10; i++)
        {
            move(all(tmp[i]), back_inserter(a));
        }
        for (auto &it : a)
            cout << it << " ";
        cout << "\n";
        q *= 10;
    }

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

7-7 第k小元素

给定一个大小为n(1≤n≤1000000)且无序的整型数组，数组中可能存在相同元素，请找出该数组第k(1≤k≤n)小的元素，注意这里的第k小元素指的是按从小到大排序后的第k个位置上的元素。

输入格式:

每个输入文件为一个测试用例，每个文件的第一行给出两个正整数n和k，第二行给出n个整数，其间以空格分隔。

输出格式:

输出第k小元素的值。

输入样例:

10 4
2 3 5 12 4 9 3 8 2 9

输出样例:

3

实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    cout<<a[k];
    return 0;
}

7-8 逆序对

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai​>aj​ 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式:

第一行，一个数 n，表示序列中有 n个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。

输出格式:

输出序列中逆序对的数目。

输入样例:

在这里给出一组输入。例如：

6
5 4 2 6 3 1

输出样例:

在这里给出相应的输出。例如：

11

提示

对于 25% 的数据，n≤2500
对于 50% 的数据，n≤4×104。
对于所有数据，n≤5×105
请使用较快的输入输出

实现代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long sum;
const int N=5e5+10;
int a[N],c[N];

void sort(int s,int l){
	if(s<l){
		int mid=(s+l)/2;
		sort(s,mid);
		sort(mid+1,l);
		int i=s,j=mid+1;
		int k=s;
		while(i<=mid&&j<=l){
			if(a[i]<=a[j]){
				c[k++]=a[i++];
			}
			else{
				c[k++]=a[j++];
				sum+=mid-i+1;
			}
		}
		while(i<=mid) c[k++]=a[i++];
		while(j<=l) c[k++]=a[j++];
		for(int j=s;j<=l;j++){
			a[j]=c[j];
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(1,n);
	cout<<sum;
	return 0;
}

7-9 堆排序

给定一个整数序列，请按非递减序输出采用堆排序的各趟排序后的结果。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。

输出格式:

对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。

输入样例:

4
8 7 2 1
8
40 55 49 73 12 27 98 81

输出样例:

7 1 2 8
2 1 7 8
1 2 7 8
81 73 49 55 12 27 40 98
73 55 49 40 12 27 81 98
55 40 49 27 12 73 81 98
49 40 12 27 55 73 81 98
40 27 12 49 55 73 81 98
27 12 40 49 55 73 81 98
12 27 40 49 55 73 81 98

实现代码：

#include <bits/stdc++.h>
using namespace std;
int a[105], n;

void print(){
    cout<<a[1];
    for (int i=2;i<=n;i++)
        cout<<" "<<a[i];
    cout<<endl;
}
void sift(int k, int end){
    int i=k,j=2*i;
    while(j<=end){
        if(j<end&&a[j]<a[j+1])j++;
        if(a[i]<a[j])swap(a[i], a[j]);
        i=j;
        j=2*i;
    }
}
void heapsort(int n){
    for(int k=n/2;k>=1;k--)
        sift(k,n);
    for(int k=1;k<n;k++){
        swap(a[1],a[n-k+1]);
        sift(1,n-k);
        print();
    }
}
int main(){
    while (~scanf("%d", &n)){
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        heapsort(n);
    }
}