基础算法训练题单之排序（从入门到入土）——题解

标签：int 题解 sum 题单 cin long 入土 include define

A. P1177 【模板】排序

三种方法：快速排序，归并排序，STL库的sort函数。

法一、三：https://www.cnblogs.com/expect-999/p/17594345.html

法二：https://www.cnblogs.com/expect-999/p/17599008.html

B. P1923 【深基9.例4】求第 k 小的数

模板题目，直接对数组进行升序排序，如果数组从零开始，则找到下标为k-1的数，从1开始的就找第K个数。
https://www.cnblogs.com/expect-999/p/18143416

C. P1271 【深基9.例1】选举学生会
直接对数组按升序排序输出即可。

点击查看C题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];

    while (i < j)
    {
        do ++i; while (q[i] < x);
        do --j; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

signed main()
{
    import;
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) cin >> q[i];

    quick_sort(q,0,m-1);

    for (int i = 0; i < m; ++i) cout << q[i] << ' ';

    return 0;
}

D. [NOIP2006 普及组] 明明的随机数
对数组进行排序，再用unique函数进行去重（这个去重其实就是重复的数字移到后面去了，并不是真正的去重）

点击查看D题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1;
    int x = q[ (l + r) >> 1];

    while (i < j)
    {
        do ++i; while (q[i] < x);
        do --j; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

signed main()
{
    import;
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) cin >> q[i];

    quick_sort(q,0,n-1);

    int k = unique(q,q + n) - q; //unique"去掉"重复的,其实返回去重后最后一个不重复元素地址
                                 //再减去首地址就是下标，
    cout << k << endl;
    for (int i = 0; i < k; ++i) cout << q[i] << " ";

    return 0;
}

E. [NOIP2007 普及组] 奖学金
利用sort和结构体来进行排序————当一个模板题理解记忆就好了。

点击查看E题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

struct stu
{
    int Id;
    int chinese;
    int math;
    int eglish;
    int sum;
}q[N];

bool cmp(stu a, stu b)
{
    if (a.sum != b.sum) return a.sum > b.sum;
    else if (a.chinese != b.chinese) return a.chinese > b.chinese;
    else return a.Id < b.Id;
}

signed main()
{
    import;
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> q[i].chinese >> q[i].math >> q[i].eglish;
        q[i].Id = i;
        q[i].sum = q[i].chinese + q[i].math + q[i].eglish;
    }

    sort(q + 1, q + n + 1, cmp);

    for (int i = 1; i <= 5; ++i) printf("%d %d\n", q[i].Id, q[i].sum);

    return 0;
}

F. 宇宙总统
同上一题一样

点击查看F题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n;

struct stu
{
    int id;
    int size;
    string x;
}q[N];

bool cmp(stu a, stu b)
{
    if (a.size != b.size) return a.size > b.size;
    else return a.x > b.x;
}

signed main()
{

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> q[i].x;
        q[i].id = i ;
        q[i].size = (q[i].x).size();
    }

    sort(q + 1, q + n + 1, cmp);

    cout << q[1].id << endl;
    cout << q[1].x << endl;
}

G. [USACO07DEC] Bookshelf B

点击查看G题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n,cnt;
int q[N];

ll h,sum;

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

signed main()
{

    cin >> n >> h;

    for (int i = 0; i < n; ++i) cin >> q[i];

    sort(q, q + n, cmp);

    for (int i = 0; i < n; ++i)
    {
        if (sum < h)
        {
            sum += q[i];
            cnt++;
        }
        else break;
    }

    cout << cnt << endl;

    return 0;
}

H. 车厢重组

点击查看H题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n;
int q[N],p[N];

ll cnt;

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int mid = l + r >> 1;

    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int i = l, j = mid+1,k=0;
    while (i<=mid && j<=r)
    {
       if(q[i]<=q[j])  p[k++] = q[i++];
       else
       {
           p[k++] = q[j++];
           cnt += mid - i + 1;
       }
    }

    while (i <= mid) p[k++] = q[i++];
    while (j <= r) p[k++] = q[j++];

    for (int i = l, k = 0; i <= r;++i) q[i] = p[k++];

}

signed main()
{

    cin >> n;

    for (int i = 0; i < n; ++i) cin >> q[i];

    merge_sort(q, 0, n-1);

    cout << cnt << endl;

    return 0;
}

I. 欢乐的跳

点击查看I题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, cnt;
int q[N], p[N];

signed main()
{

    cin >> n;

    for (int i = 0; i < n; ++i) cin >> q[i];

    for (int i = 0; i < n - 1; ++i) p[++cnt] = abs(q[i] - q[i + 1]);

    sort(p + 1, p + cnt + 1);

    int ok = 1;
    for (int i = 1; i < n; ++i)
    {
        if (p[i] != i)
        {
            ok = 0;
            break;
        }
    }

    if (ok) cout << "Jolly" << endl;
    else cout << "Not jolly" << endl;

    return 0;
}

J. [NOIP2009 普及组] 分数线划定

点击查看J题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, m;

struct stu
{
    int v;
    int p;
}q[N];

bool cmp(stu a, stu b)
{
    if (a.p == b.p) return a.v < b.v;
    else return a.p > b.p;
}

signed main()
{

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) cin >> q[i].v >> q[i].p;

    int k = m * 1.5;

    sort(q+1, q + n + 1, cmp);

    for (int i = k; i <= n; ++i)
    {
        if (q[i].p == q[i + 1].p) k++;
        else break;
    }

    printf("%d %d\n", q[k].p, k);
    for (int i = 1; i <= k; ++i) printf("%d %d\n", q[i].v, q[i].p);

    return 0;
}

K. 攀爬者

点击查看K题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, m;
double sum;

struct stu
{
    int x;
    int y;
    int z;
}q[N];

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

signed main()
{

    cin >> n ;

    for (int i = 0; i < n; ++i) cin >> q[i].x >> q[i].y >> q[i].z;

    sort(q, q + n, cmp);

    for (int i = 0; i < n-1; ++i)
    {
        int x1 = pow(q[i].x - q[i + 1].x, 2);
        int y1 = pow(q[i].y - q[i + 1].y, 2);
        int z1 = pow(q[i].z - q[i + 1].z, 2);
        double p = pow(x1 + y1 + z1, 1.0 / 2);
        sum += p;
    }

    printf("%.3lf", sum);

    return 0;
}

L. 生日

点击查看L题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, m;
double sum;

struct stu
{
    string name;
    int year;
    int month;
    int day;
    int id;
}q[N];

bool cmp(stu a, stu b)
{
    if (a.year != b.year) return a.year < b.year;
    else if (a.month != b.month) return a.month < b.month;
    else if (a.day != b.day) return a.day < b.day;
    else return a.id > b.id;
}

signed main()
{

    cin >> n ;

    for (int i = 0; i < n; ++i)
    {
        cin >> q[i].name >> q[i].year >> q[i].month >> q[i].day;
        q[i].id = i;
    }

    sort(q, q + n, cmp);

    for (int i = 0; i < n; ++i) cout << q[i].name << endl;

    return 0;
}

M. [NOIP1998 提高组] 拼数

点击查看M题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, m;
string q[N];

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

signed main()
{
    import;
    cin >> n;

    for (int i = 0; i < n; ++i) cin >> q[i];

    sort(q, q + n,cmp);

    for (int i = 0; i < n; ++i) cout << q[i];

    return 0;
}

N. [NOIP2005 提高组] 谁拿了最多奖学金

点击查看N题代码

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n;

struct stu
{
	int id;
	string name;
	int egrade,pgrade;
	char cadre,west;
	int papernum;
	int sum;
}q[N];

bool cmp(stu a, stu b)
{
	if (a.sum != b.sum) return a.sum > b.sum;
	else return a.id < b.id;
}


signed main()
{

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		q[i].id = i;
		cin >> q[i].name >> q[i].egrade >> q[i].pgrade >> q[i].cadre >> q[i].west >> q[i].papernum;
		if (q[i].papernum >= 1 && q[i].egrade > 80) q[i].sum += 8000;
		if (q[i].egrade > 85 && q[i].pgrade > 80) q[i].sum += 4000;
		if (q[i].egrade > 90) q[i].sum += 2000;
		if (q[i].west == 'Y' && q[i].egrade > 85) q[i].sum += 1000;
		if (q[i].cadre == 'Y' && q[i].pgrade > 80) q[i].sum += 850;
	}

	sort(q, q + n,cmp);

	cout << q[0].name << endl;

	int ans = 0;
	for (int i = 0; i < n; ++i)
	{
		ans += q[i].sum;
	}

	printf("%d\n%d", q[0].sum,ans);

	return 0;
}

O. [NOIP2011 普及组] 瑞士轮
https://www.cnblogs.com/expect-999/p/18162711
P. 逆序对
https://www.cnblogs.com/expect-999/p/18143932

以上就是此次排序训练的全部内容了，希望你有所收获。

标签：int,题解,sum,题单,cin,long,入土,include,define
From： https://www.cnblogs.com/expect-999/p/18290781

基础算法训练题单之排序（从入门到入土）——题解

相关文章

赞助商

阅读排行