排序

排序的基本概念，小的在前，大的在后
3种 $O(n^2)$ 的排序
3种 $O(n \log n)$ 的排序
结构体排序

3个 $O(n^2)$ 的排序

冒泡排序
选择排序
插入排序

3个 $O(n \log n)$ 的排序

3个不基于比较的排序

计数排序
基数排序
桶排序（分段计数排序）

其他排序

内省排序 (introsort)
希尔排序
锦标赛排序

冒泡排序

https://oi-wiki.org/basic/bubble-sort/
基本没用，了解概念即可
最好情况下，冒泡排序的时间复杂度？
最坏情况下，冒泡排序的时间复杂度？
平均情况下，冒泡排序的时间复杂度？
冒泡排序的额外空间复杂度？
冒泡排序的交换次数和逆序对个数的关系？
冒泡排序是稳定排序吗？

$O(n^2)$

for (int i = 0; i < n; i++)
{
    for (int j = 1; j < n; j++)
    {
        if (a[j - 1] > a[j])
        {
            swap(a[j - 1], a[j]);
        }
    }
}

交换的次数 = 逆序对的个数
a[i] > a[j] && i < j 的个数

选择排序

https://oi-wiki.org/basic/selection-sort/
基本没用，了解概念即可
最好情况下，选择排序的时间复杂度？
最坏情况下，选择排序的时间复杂度？
平均情况下，选择排序的时间复杂度？
选择排序的额外空间复杂度？
选择排序是稳定排序吗？
（直接实现的版本是不稳定的，如果不用交换，而是保持剩余的数字原序，那么是稳定的）
对一个排列进行选择排序，交换次数如何计算？
排序长度为L的环，需要交换L-1
对于一个排列进行排序的最小交换次数等于所有环长-1 的和

插入排序

https://oi-wiki.org/basic/insertion-sort/
基本没用，了解概念即可
最好情况下，插入排序的时间复杂度？
最坏情况下，插入排序的时间复杂度？
平均情况下，插入排序的时间复杂度？
插入排序的额外空间复杂度？
插入排序是稳定排序吗？

如果数组几乎有序，插入排序的效率很高

快速排序

时间复杂度 $O(n \log n)$
（额外）空间复杂度 $O(\log n)$
衍生出求第 $k$ 小数 $O(n)$
STL函数 nth_element

堆排序

时间复杂度 $O(n \log n)$
（额外）空间复杂度 $O(1)$
最坏时间复杂度 $O(n \log n)$
$O(n)$ 建堆，pop $n$ 次

归并排序

时间复杂度 $O(n \log n)$
（额外）空间复杂度 $O(n)$
可以求逆序对 $O(n \log n)$
可以用硬盘，不一定都要在内存
可以从2个文件中读入，输出到第3个文件
比如你需要排序非常非常大的文件，10G

Linux 系统自带的排序命令 sort 就是使用归并排序

sort

实际题目需要排序的话，几乎一定直接STL sort 函数
STL sort 函数使用 introsort 效率非常高
intro sort 是快排堆排选择排序结合在一起的
主要掌握排序结构体时，比较函数如何实现，有三种方式

重载运算符
自定义比较函数
仿函数

任意2个元素必须可以比较，如果不可以比较当做等于
比较全序关系
a < b && b < c 那么 a < c
a == b && b == c 那么也要a == c

稳定性

稳定排序：相等的元素保持原序
不稳定排序：相等的元素无法保持原序
不是指时间复杂度！！

任意2个元素必须可以比较，如果不可以比较当做等于
比较全序关系
a < b && b < c 那么 a < c
a == b && b == c 那么也要a == c

使用 vector 分组

如果排序的数字都是整数，并且范围很小
输入一个长度为n的数组
输入m个询问，每个询问是一个区间[L, R]
将所有区间，按照左端点排序
vector<pair<int, int> >b[100020];
for (int i = 1; i <= m; i++)
{
cin >> L >> R:
b[L].push_back(make_pair(i, R));
}

分段计数排序
计数相当于只能排1维

多关键字计数排序

排 (x, y)
计数排序支持：按x排序，如果x相同，那么保持原序

如果想先比较x，再比较y，那就排序2次
第一次按y排序，（如果y相等，按输入顺序）
第二次按x排序，（如果x相等，按第一次的顺序也就是y的顺序，如果再相等，按输入顺序）

离散化

逆序对

相关题目

P1059 [NOIP2006 普及组] 明明的随机数

https://www.luogu.com.cn/problem/P1059

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N≤100)$ ，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$ ，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

8
15 20 32 40 67 89 300 400

提示

NOIP 2006 普及组第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	n = unique(a, a + n) - a;
	printf("%d\n", n);
	for (int i = 0; i < n; i++) {
		printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

排序去重

用set，去重
注意到a[i]范围很小，统计每个数字是否出现过
sort unique
sort(a, a + n);
n = unique(a, a + n) - a;

unique 是不排序的

set / TreeSet
sort unique
array

100 300 200 400 -> 1 3 2 4
sort unique lower_bound

P1296 奶牛的耳语

https://www.luogu.com.cn/problem/P1296

题目描述

在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 $n$ 头奶牛，其中第 $i$ 头牛在直线上所处的位置可以用一个整数坐标 $p_i(0\le p_i \le 10^8)$ 来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 $d(0 \le d \le 10^4)$ 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 $d$ ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

输入格式

第一行包含两个整数 $n,d$ 。

第二行包含 $n$ 个整数，每个整数都是一个坐标 $p_i$ ，描述一头奶牛在直线上的位置。

输出格式

一个数，表示养牛场中可以相互交流奶牛的对数。

样例 #1

样例输入 #1

5 10
10 12 16 37 40

样例输出 #1

提示

数据规模

对于 $40\%$ 的数据， $1 \leq n \leq 10^3$ 。

对于 $100\%$ 的数据， $1 \leq n \leq 10^6$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, d, a[1000020];
long long z;
int main()
{
	scanf("%d%d", &n, &d);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0, j = 0; i < n; i++)
	{
		while (a[i] - a[j] > d)
		{
			j++;
		}
		z += i - j;
	}
	printf("%lld\n", z);
	return 0;
}

题解

二分/双指针法

二分
统计每个数字p[i]前面有几个p[j]使得p[i]-p[j] <= d
统计每个数字p[i]后面有几个p[j]使得p[j]-p[i] <= d
双指针法

CF670C Cinema

https://codeforces.com/problemset/problem/670/C
https://www.luogu.com.cn/problem/CF670C

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
map<int, int> g;
int b[200020];
int c[200020];
int zi, zb, zc;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		g[x]++;
	}
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> b[i];
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> c[i];
	}
	zi = zb = zc = -1;
	for (int i = 1; i <= m; i++)
	{
		if (zb < g[b[i]] || zb == g[b[i]] && zc < g[c[i]])
		{
			zb = g[b[i]];
			zc = g[c[i]];
			zi = i;
		}
	}
	cout << zi << endl;
}

题解

有n个人，第i个人会语言a[i]，有m个电影，第j个电影的语音是b[j]，字幕是c[j]
问选哪个电影，可以让最多的人听懂或看懂，输入电影下标，如果多个答案输入任意一个都可以

abc213_c Reorder Cards

https://atcoder.jp/contests/abc213/tasks/abc213_c

参考代码

#include <bits/stdc++.h>
using namespace std;
int h, w, n, ac, bc;
int a[100020];
int aa[100020];
int b[100020];
int bb[100020];
int main()
{
	cin >> h >> w >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
		aa[i] = a[i];
		bb[i] = b[i];
	}
	sort(aa, aa + n);
	sort(bb, bb + n);
	ac = unique(aa, aa + n) - aa;
	bc = unique(bb, bb + n) - bb;
	for (int i = 0; i < n; i++)
	{
		a[i] = lower_bound(aa, aa + ac, a[i]) - aa;
		b[i] = lower_bound(bb, bb + bc, b[i]) - bb;
		cout << a[i] + 1 << ' ' << b[i] + 1 << endl;
	}
	return 0;
}

题解

输入两个长度为n个序列a[i]和b[i]，希望保持数组中相对大小关系不变，并把值域缩小。
输出缩小之后的结果

abc221_d Online games

https://atcoder.jp/contests/abc221/tasks/abc221_d

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, y, s;
pair<int, int> a[400020];
int z[200020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;
		a[i + n] = make_pair(x, +1);
		a[i] = make_pair(x + y, -1);
	}
	sort(a, a + 2 * n);
	for (int i = 0; i + 1 < 2 * n; i++)
	{
		s += a[i].second;
		z[s] += a[i + 1].first - a[i].first; 
	}
	for (int i = 1; i <= n; i++)
	{
		cout << z[i] << " ";
	}
	cout << endl;
	return 0;
}

题解

输入n个区间，输出n个数字，第k个数字表示被覆盖k次的长度

P4604 [WC2017]挑战

https://www.luogu.com.cn/problem/P4604

题目背景

滥用本题评测将被封号。洛谷不保证此类毒瘤题的评测结果准确性。

你和同学们找了三道题目用来练习。

这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。

同学们纷纷写出了优秀的代码。现在，他们向你发起了挑战，他们对每个问题都设置了若干个测试数据，这是他们能通过的最大规模的测试数据。现在，他们想看一看你写的代码究竟能超过多少同学的代码，通过多大规模的测试数据。

本题分为 $3$ 个任务，每个任务对应一道题和相应的若干个测试点，你需要对于每个任务，设计一个能通过尽量多测试点的程序。

题目描述

任务一

给定 $n$ 个 $32$ 位无符号整数，将它们从小到大排序。

任务二

有 $2n$ 个人在玩「石头剪刀布」游戏。他们排成两排，每排 $n$ 个人。每个人在每一局游戏都使用固定策略，即对于第 $i (i \in 1, 2)$ 排的第 $j (0 \leq j < n)$ 个人，用一个整数 $a_{ij}$ 表示他的策略，其中 $0$ 表示只出石头， $1$ 表示只出剪刀， $2$ 表示只出布。

现在有 $q$ 个询问，每个询问给定三个整数 $x,y,l(0\leq x,y<n,1\leq l\leq n-max(x,y))$ ，问将第一排的第 $x∼x+l-1$ 个人和第二排的第 $y∼y+l-1$ 个人比赛之后，第一排有多少个人会赢。

上文中「比赛」的意思是，对于所有整数 $i$ 满足 $0\leq i<l$ ,让第一排的第 $x+i$ 个人和第二排的第 $y+i$ 个人进行「石头剪刀布」游戏。

任务三

我们称一个合法的括号串为：只由左括号和右括号构成，两种括号的数量相等，且任意一个前缀的左括号数量不少于右括号数量的串。现在给定一个由 (，) 和? 构成的串，问有多少种不同的方案，使得将每个 ? 都替换成一个括号之后，该串变成一个合法的括号串。两种方案不同，当且仅当至少有一个位置的 ? 被替换成了不同的括号。

输入格式

此题提供了模板程序。选手可以在此基础上编写自己的程序，模板程序详见下文数据范围与提示。

第一行一个整数 $task\_id(1\leq task\_id\leq3)$ ，表示任务编号。接下来是每个具体任务的输入内容。

在输入的同一行中，相邻的两个整数会被一个空格隔开。

对于任务一：一行，两个整数 $n,s$ 。令 $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i<n$ ，则 $a_0,a_1,…,a_{n-1}$ 即为需要排序的 $n$ 个整数。

对于任务二：第一行两个整数 $n,q$ 。第二行一个仅包含 $0, 1, 2$ 的长度为 $n$ 的字符串，第 $i$ 个字符所代表的整数表示第一排第 $i$ 个人的策略（即 $a_{1i}$ ）。第三行格式同第二行，表示第二排各个人的策略。

对于任务三：第一行一个整数 $n$ ，表示给定的串的长度。第二行一个字符串，即为给定的串。

输出格式

对于任务1：令 $b$ 为已经排好序的数组，调用 output_arr(b, n * 4) 即可。

对于任务2：将每个询问的答案依次存入 $32$ 位无符号整数数组 $b$ 中（即，存入 $b_0,b_1,⋯,b_{q-1}$ 中），然后调用 output_arr(b, q * 4) 即可。

对于任务3：输出一个整数，表示不同的方案数除以 $2^{32}$ 得到的余数。

样例 #1

样例输入 #1

1
100000 2017012501

样例输出 #1

4275990336

样例 #2

样例输入 #2

样例输出 #2

3349208141

样例 #3

样例输入 #3

3
4
(???

样例输出 #3

样例 #4

样例输入 #4

3
4
)???

样例输出 #4

提示

数据范围与提示

任务编号	分值	测试点编号	数据范围与约定	时间限制
1	5	1	$n=100000$	3s
1	19	2	$n=10^8$	4s
1	11	3	$n=2\times10^8$	6s
2	7	4	$n=q=1000$	3s
2	23	5	$n=q=300000$	3s
3	9	6	$n=1000$	3s
3	5	7	$n=120000$	3s
3	7	8	$n=225000$	3s
3	14	9	$n=266666$	3s

模板程序

C++模板

#include <stdio.h>
#include <string.h>
#include <algorithm>

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    for (u32 i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

namespace Sorting {
void init_data(u32 *a, int n, u32 seed) {
    for (int i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }
}

void main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = new u32[n];
    init_data(a, n, seed);

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}
}

namespace Game {
void main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = new char[n + 1];
    char *s2 = new char[n + 1];
    scanf("%s%s", s1, s2);

    u32 *anss = new u32[q];
    int *q_x = new int[q];
    int *q_y = new int[q];
    int *q_len = new int[q];

    for (int i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}
}

namespace Parentheses {
void main() {
    int n;
    scanf("%d", &n);

    char *s = new char[n + 1];
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting::main();
            break;
        case 2:
            Game::main();
            break;
        case 3:
            Parentheses::main();
            break;
    }

    return 0;
}

C模板

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define bool int
#define true 1
#define false 0

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    u32 i;
    for (i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

void Sorting_main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = malloc(n * sizeof(u32));
    int i;
    for (i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}

void Game_main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = malloc((n + 1) * sizeof(char));
    char *s2 = malloc((n + 1) * sizeof(char));
    scanf("%s%s", s1, s2);

    u32 *anss = malloc(q * sizeof(u32));
    int *q_x = malloc(q * sizeof(int));
    int *q_y = malloc(q * sizeof(int));
    int *q_len = malloc(q * sizeof(int));

    int i;

    for (i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}

void Parentheses_main() {
    int n;
    scanf("%d", &n);

    char *s = malloc((n + 1) * sizeof(char));
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting_main();
            break;
        case 2:
            Game_main();
            break;
        case 3:
            Parentheses_main();
            break;
    }

    return 0;
}

Pascal模板

type
    u32 = dword;
    u64 = qword;
    u32_p = ^u32;
    u64_p = ^u64;
    longint_p = ^longint;

function next_integer(x : u32) : u32; inline;
begin
    x := x xor (x << 13);
    x := x xor (x >> 17);
    x := x xor (x << 5);
    exit(x);
end;

function output_arr(a_in : pointer; size : u32) : boolean;
var
    blocks : u32;
    a, a_ed : u32_p;
    ret, x : u32;
begin
    if size mod 4 <> 0 then begin
        writeln(-1);
        exit(false);
    end;

    blocks := size div 4;
    ret := size;
    a := a_in;
    a_ed := a + blocks;
    x := 23333333;

    while a < a_ed do begin
        ret := ret xor (a[0] + x);
        x := x xor (x << 13);
        x := x xor (x >> 17);
        x := x xor (x << 5);
        inc(a);
    end;

    writeln(ret);
    exit(true);
end;

// ====== header ======


procedure init_data(a : u32_p; n : longint; seed : u32);
var
    a_ed : u32_p;
begin
    a_ed := a + n;
    while a < a_ed do begin
        seed := next_integer(seed);
        a[0] := seed;
        inc(a);
    end;
end;

procedure Sorting_main();
var
    n : longint;
    seed : u32;
    a : u32_p;
    i : u32;
begin
    read(n, seed);

    a := Getmem(n * sizeof(u32));
    init_data(a, n, seed);

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
end;


procedure Game_main();
var
    n, q : longint;
    s1, s2 : ansistring;
    anss : u32_p;
    q_x, q_y, q_len : longint_p;
    i : longint;
begin
    readln(n, q);
    readln(s1);
    readln(s2);

    anss := Getmem(q * sizeof(u32));
    q_x := Getmem(q * sizeof(longint));
    q_y := Getmem(q * sizeof(longint));
    q_len := Getmem(q * sizeof(longint));

    for i := 0 to q - 1 do begin
        read(q_x[i], q_y[i], q_len[i]);
    end;

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
end;


procedure Parentheses_main();
var
    n : longint;
    s : ansistring;
    ans : u32;
begin
    read(n);
    read(s);

    // ans := solve(n, s);

    writeln(ans);
end;


var
    task_id : longint;

begin
    read(task_id);

    if task_id = 1 then begin
        Sorting_main();
    end else if task_id = 2 then begin
        Game_main();
    end else if task_id = 3 then begin
        Parentheses_main();
    end;
    close(input); close(output);
end.

参考代码

题解

P1138 第 k 小整数

https://www.luogu.com.cn/problem/P1138

题目描述

现有 $n$ 个正整数，要求出这 $n$ 个正整数中的第 $k$ 个最小整数（相同大小的整数只计算一次）。

输入格式

第一行为 $n$ 和 $k$ ; 第二行开始为 $n$ 个正整数的值，整数间用空格隔开。

输出格式

第 $k$ 个最小整数的值；若无解，则输出 NO RESULT。

样例 #1

样例输入 #1

10 3
1 3 3 7 2 5 1 2 4 6

样例输出 #1

提示

$n \leq 10000$ ， $k \leq 1000$ ，正整数均小于 $30000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, a[10000];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	n = unique(a, a + n) - a;
	k--;
	if (k < n) {
		printf("%d\n", a[k]);
	} else {
		printf("NO RESULT\n");
	}
	return 0;
}

题解

排序

P1097 [NOIP2007 提高组] 统计数字

https://www.luogu.com.cn/problem/P1097

题目背景

警告：数据可能存在加强

题目描述

某次科研调查时得到了 $n$ 个自然数，每个数均不超过 $1500000000(1.5 \times 10^9)$ 。已知不相同的数不超过 $10000$ 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

共 $n+1$ 行。

第一行是整数 $n$ ，表示自然数的个数；

第 $2$ 至 $n+1$ 每行一个自然数。

输出格式

共 $m$ 行（ $m$ 为 $n$ 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出 $2$ 个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例 #1

样例输入 #1

样例输出 #1

提示

$40\%$ 的数据满足： $1 \le n \le 1000$

$80\%$ 的数据满足： $1 \le n \le 50000$

$100\%$ 的数据满足： $1 \le n \le 200000$ ，每个数均不超过 $1500 000 000(1.5 \times 109)$

NOIP 2007 提高第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int n, x;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		g[x]++;
	}
	for (map<int, int>::iterator i = g.begin(); i != g.end(); i++) {
		printf("%d %d\n", i->first, i->second);
	}
	return 0;
}

题解

map
排序

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

https://www.luogu.com.cn/problem/P1051

题目描述

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

院士奖学金，每人 $8000$ 元，期末平均成绩高于 $80$ 分（ $>80$ ），并且在本学期内发表 $1$ 篇或 $1$ 篇以上论文的学生均可获得；
五四奖学金，每人 $4000$ 元，期末平均成绩高于 $85$ 分（ $>85$ ），并且班级评议成绩高于 $80$ 分（ $>80$ ）的学生均可获得；
成绩优秀奖，每人 $2000$ 元，期末平均成绩高于 $90$ 分（ $>90$ ）的学生均可获得；
西部奖学金，每人 $1000$ 元，期末平均成绩高于 $85$ 分（ $>85$ ）的西部省份学生均可获得；
班级贡献奖，每人 $850$ 元，班级评议成绩高于 $80$ 分（ $>80$ ）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 $87$ 分，班级评议成绩 $82$ 分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是 $4850$ 元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

输入格式

第一行是 $1$ 个整数 $N(1 \le N \le 100)$ ，表示学生的总数。

接下来的 $N$ 行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 $20$ 的字符串（不含空格）；期末平均成绩和班级评议成绩都是 $0$ 到 $100$ 之间的整数（包括 $0$ 和 $100$ ）；是否是学生干部和是否是西部省份学生分别用 $1$ 个字符表示， $Y$ 表示是， $N$ 表示不是；发表的论文数是 $0$ 到 $10$ 的整数（包括 $0$ 和 $10$ ）。每两个相邻数据项之间用一个空格分隔。

输出格式

包括 $3$ 行。

第 $1$ 行是获得最多奖金的学生的姓名。

第 $2$ 行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。

第 $3$ 行是这 $N$ 个学生获得的奖学金的总数。

样例 #1

样例输入 #1

4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

样例输出 #1

ChenRuiyi
9000
28700

提示

【题目来源】

NOIP 2005 提高组第一题

参考代码

题解

模拟

P1080 [NOIP2012 提高组] 国王游戏

https://www.luogu.com.cn/problem/P1080

题目描述

恰逢 $H$ 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 $n$ ，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$ ，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$ ，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例 #1

样例输入 #1

样例输出 #1

提示

【输入输出样例说明】

按 $1$ 、 $2$ 、 $3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$ ；

按 $1$ 、 $3$ 、 $2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$ ；

按 $2$ 、 $1$ 、 $3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$ ；

按 $2$ 、 $3$ 、 $1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$ ；

按 $3$ 、 $1$ 、 $2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$ ；

按 $3$ 、 $2$ 、 $1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$ 。

因此，奖赏最多的大臣最少获得 $2$ 个金币，答案输出 $2$ 。

【数据范围】

对于 20%的数据，有 $1≤ n≤ 10,0 < a,b < 8$ ；

对于 40%的数据，有 $1≤ n≤20,0 < a,b < 8$ ；

对于 60%的数据，有 $1≤ n≤100$ ；

对于 60%的数据，保证答案不超过 $10^9$ ；

对于 100%的数据，有 $1 ≤ n ≤1,000,0 < a,b < 10000$ 。

NOIP 2012 提高组第一天第二题

参考代码

题解

国王游戏。按乘积排序然后计算答案。
需要高精度或 Python

P1068 [NOIP2009 普及组] 分数线划定

https://www.luogu.com.cn/problem/P1068

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才， $A$ 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m \times 150\%$ （向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 $n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n)$ ，中间用一个空格隔开，其中 $n$ 表示报名参加笔试的选手总数， $m$ 表示计划录取的志愿者人数。输入数据保证 $m \times 150\%$ 向下取整后小于等于 $n$ 。

第二行到第 $n+1$ 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 $k(1000 ≤ k ≤ 9999)$ 和该选手的笔试成绩 $s(1 ≤ s ≤ 100)$ 。数据保证选手的报名号各不相同。

输出格式

第一行，有 $2$ 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 $2$ 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例说明】

$m \times 150\% = 3 \times150\% = 4.5$ ，向下取整后为 $4$ 。保证 $4$ 个人进入面试的分数线为 $88$ ，但因为 $88$ 有重分，所以所有成绩大于等于 $88$ 的选手都可以进入面试，故最终有 $5$ 个人进入面试。

NOIP 2009 普及组第二题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
pair<int, int> a[100020];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].second, &a[i].first);
		a[i].first = -a[i].first;
	}
	sort(a, a + n);
	k = min(k * 3 / 2, n);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (-a[i].first >= -a[k - 1].first) {
			cnt++;
		}
	}
	printf("%d %d\n", -a[cnt - 1].first, cnt);
	for (int i = 0; i < n; i++) {
		if (-a[i].first >= -a[k - 1].first) {
			printf("%d %d\n", a[i].second, -a[i].first);
		}
	}
	return 0;
}

题解

模拟

P1102 A-B 数对

https://www.luogu.com.cn/problem/P1102

题目描述

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

好吧，题目是这样的：给出一串数以及一个数字 $C$ ，要求计算出所有 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个整数 $N, C$ 。

第二行， $N$ 个整数，作为要求处理的那串数。

输出格式

一行，表示该串数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

提示

对于 $75\%$ 的数据， $1 \leq N \leq 2000$ 。

对于 $100\%$ 的数据， $1 \leq N \leq 2 \times 10^5$ 。

保证所有输入数据绝对值小于 $2^{30}$ ，且 $C \ge 1$ 。

2017/4/29 新添数据两组

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[200020];
int n, c;
long long z;
int main()
{
	scanf("%d%d", &n, &c);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
	}
	printf("%lld\n", z);
	return 0;
}

题解

map
排序

P3913 车的攻击

https://www.luogu.com.cn/problem/P3913

题目描述

$N \times N$ 的国际象棋棋盘上有 $K$ 个车，第 $i$ 个车位于第 $R_i$ 行，第 $C_i$ 列。求至少被一个车攻击的格子数量。

车可以攻击所有同一行或者同一列的地方。

输入格式

第1 行，2 个整数 $N,K$ 。

接下来K 行，每行2 个整数 $R_i,C_i$ 。

输出格式

1 个整数，表示被攻击的格子数量。

样例 #1

样例输入 #1

3 2
1 2
2 2

样例输出 #1

提示

• 对于30% 的数据， $1 \le N \le 10^3; 1 \le K \le 10^3$ ；

• 对于60% 的数据， $1 \le N \le 10^6; 1 \le K \le 10^6$ ；

• 对于100% 的数据， $1 \le N \le 10^9; 1 \le K \le 10^6; 1 \le R_i , C_i \le N$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n;
int m;
int x[1000020], xc;
int y[1000020], yc;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &x[i], &y[i]);
	}
	sort(x, x + m);
	sort(y, y + m);
	xc = unique(x, x + m) - x;
	yc = unique(y, y + m) - y;
	printf("%lld\n", n * n - (n - xc) * (n - yc));
	return 0;
}

题解

行去重
列去重
sort 比 set 快很多

只是为了去重，而不需要有序的话，Hash也是很好的选择。

P4305 [JLOI2011]不重复数字

https://www.luogu.com.cn/problem/P4305

题目描述

给定 $n$ 个数，要求把其中重复的去掉，只保留第一次出现的数。

输入格式

本题有多组数据。

第一行一个整数 $T$ ，表示数据组数。

对于每组数据：

第一行一个整数 $n$ 。

第二行 $n$ 个数，表示给定的数。

输出格式

对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。

样例 #1

样例输入 #1

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

样例输出 #1

1 2 18 3 19 6 5 4
1 2 3 4 5 6

提示

对于 $30\%$ 的数据， $n \le 100$ ，给出的数 $\in [0, 100]$ 。

对于 $60\%$ 的数据， $n \le 10^4$ ，给出的数 $\in [0, 10^4]$ 。

对于 $100\%$ 的数据， $1 \le T\le 50$ ， $1 \le n \le 5 \times 10^4$ ，给出的数在 $32$ 位有符号整数范围内。

参考代码

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}
int t, n, x;
int main()
{
	t = read();
	for (int tt = 0; tt < t; tt++)
	{
		unordered_set<int> s;
		n = read();
		for (int i = 0; i < n; i++)
		{
			x = read();
			if (s.insert(x).second)
			{
				printf("%d ", x);
			}
		}
		printf("\n");
	}
	return 0;
}

题解

set暴力，
unordered_set
unordered_map
没有有序的性质了（不能lower_bound upper_bound）
不需要指定
出题人能不能造一个数据，让unordered_set超时？
能

P1469 找筷子

https://www.luogu.com.cn/problem/P1469

题目描述

经过一段时间的紧张筹备，电脑小组的“RP 餐厅”终于开业了，这天，经理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题:筷子！

CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？

输入格式

第一行是一个整数，表示筷子的数量 $n$ 。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 根筷子的长度 $a_i$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

9
2 2 1 3 3 3 2 3 1

样例输出 #1

提示

数据规模与约定

对于 $30\%$ 的数据，保证 $n \leq 10^5$ 。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^7 + 1$ ， $1 \leq a_i \leq 10^9$ 。

提示

请注意数据读入对程序效率造成的影响。
请注意本题的空间限制为 $4$ Mb。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z, x;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		z ^= x;
	}
	printf("%d\n", z);
	return 0;
}

题解

xor
(a xor a) == 0
(a xor b) == (b xor a)
(a xor b) xor c = a xor (b xor c)
如果不卡空间 map暴力 / 排序

思考题：如果只有1个出现1次，其他都是3次怎么做？

P1866 编号

https://www.luogu.com.cn/problem/P1866

题目描述

太郎有N只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子i想要一个整数，介于1和Maxnumber[i]之间（包括1和Maxnumber[i]）。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。

你只用输出答案mod 1000000007即可。如果这是不可能的，就输出0.

输入格式

第一行是一个整数N。（1≤N≤50）

第二行N个整数Maxnumber[i]。（1≤Maxnumber[i]≤1000）

输出格式

一个整数

样例 #1

样例输入 #1

2
5 8

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[60], p = 1000000007;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	long long z = 1;
	for (int i = 0; i < n; i++) {
		z = z * (a[i] - i) % p;
	}
	printf("%lld\n", z);
	return 0;
}

题解

排序，算数

P1007 独木桥

https://www.luogu.com.cn/problem/P1007

题目背景

战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

题目描述

突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 $L$ ，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$ ，但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置，他就离开了独木桥。

每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。

由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

输入格式

第一行：一个整数 $L$ ，表示独木桥的长度。桥上的坐标为 $1\cdots L$ 。

第二行：一个整数 $N$ ，表示初始时留在桥上的士兵数目。

第三行：有 $N$ 个整数，分别表示每个士兵的初始坐标。

输出格式

只有一行，输出 $2$ 个整数，分别表示部队撤离独木桥的最小时间和最大时间。 $2$ 个整数由一个空格符分开。

样例 #1

样例输入 #1

4
2
1 3

样例输出 #1

2 4

提示

初始时，没有两个士兵同在一个坐标。

数据范围 $1\le L\le5\times 10^3$ ， $0\le N\le5\times10^3$ ，数据保证 $N\le L$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int l, n, x, y, z;
int main() {
	scanf("%d%d", &l, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		y = max(y, min(x, l + 1 - x));
		z = max(z, max(x, l + 1 - x));
	}
	printf("%d %d\n", y, z);
	return 0;
}

题解

P5835 [USACO19DEC]Meetings S

https://www.luogu.com.cn/problem/P5835

题目描述

有两个牛棚位于一维数轴上的点 $0$ 和 $L$ 处。同时有 $N$ 头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 $i$ 初始时位于某个位置 $x_i$ ，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 $1$ 或 $-1$ 的整数 $d_i$ 表示。每头奶牛还拥有一个在范围 $[1,10^3]$ 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

如果奶牛 $i$ 移动到了一个牛棚，则奶牛 $i$ 停止移动。
当奶牛 $i$ 和 $j$ 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 $i$ 被赋予奶牛 $j$ 先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。

令 $T$ 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 $0 \ldots T$ （包括时刻 $T$ ）之间发生的奶牛对相遇的总数。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $L$ 。

以下 $N$ 行，每行包含三个空格分隔的整数 $w_i$ ， $x_i$ 以及 $d_i$ 。所有的位置 $x_i$ 各不相同，并且满足 $0<x_i<L$ 。

输出格式

输出一行，包含答案。

样例 #1

样例输入 #1

样例输出 #1

提示

关于部分分：

测试点 $1$ 样例。

测试点 $2\sim 4$ 满足 $N\le 10^2$ ，并且对所有 $i$ ， $w_i=1$ 。

测试点 $5\sim 7$ 满足 $N\le 10^2$ 。

对于 $100\%$ 的数据， $1\le L\le 10^9$ ， $1\le N\le 5\cdot 10^4$ 。

供题：Benjamin Qi

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
pair<int, int> b[100020];
pair<int, int> w[100020];
int n, l;
long long calc()
{
	long long re = 0;
	long long cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (b[i].second == -1)
		{
			cnt++;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (b[i].second == -1)
		{
			cnt--;
		}
		else
		{
			re += cnt;
		}
	}
	return re;
}
int main()
{
	int sum = 0, cur = 0;
	scanf("%d%d", &n, &l);
	int L = 0;
	int R = n;
	for (int i = 0; i < n; i++)
	{
		int d;
		scanf("%d%d%d", &w[i].second, &w[i].first, &d);
		b[i].first = w[i].first;
		b[i].second = d;
		sum += w[i].second;
		if (d == -1)
		{
			a[i] = make_pair(w[i].first, 0); // left;
		}
		else
		{
			a[i] = make_pair(l - w[i].first, 1); // right;
		}
	}
	sort(w, w + n);
	sort(a, a + n);
	int tim = -1;
	for (int i = 0; i < n; i++)
	{
		if (a[i].second == 0)
		{
			cur += w[L++].second;
		}
		else
		{
			cur += w[--R].second;
		}
		if (cur * 2 >= sum)
		{
			tim = a[i].first;
			break;
		}
	}
	sort(b, b + n);
	long long ans = calc();
	for (int i = 0; i < n; i++)
	{
		b[i].first += b[i].second * tim;
	}
	sort(b, b + n);
	ans -= calc();
	printf("%lld\n", ans);
	return 0;
}

题解

相遇调头

P1094 [NOIP2007 普及组] 纪念品分组

https://www.luogu.com.cn/problem/P1094

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 $n+2$ 行：

第一行包括一个整数 $w$ ，为每组纪念品价格之和的上上限。

第二行为一个整数 $n$ ，表示购来的纪念品的总件数 $G$ 。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

样例 #1

样例输入 #1

样例输出 #1

提示

$50\%$ 的数据满足： $1\le n\le15$ 。

$100\%$ 的数据满足： $1\le n\le3\times10^4$ ， $80\le w\le200$ ， $5 \le P_i \le w$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int w, n, a[100020], z;
int main() {
	scanf("%d%d", &w, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = n - 1; i >= z; i--) {
		if (i > z && a[i] + a[z] <= w) {
			z++;
		}
	}
	printf("%d\n", n - z);
	return 0;
}

题解

双指针法

P1093 [NOIP2007 普及组] 奖学金

https://www.luogu.com.cn/problem/P1093

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:

$7$ $279$
$5$ $279$

这两行数据的含义是:总分最高的两个同学的学号依次是 $7$ 号、 $5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。如果你的前两名的输出数据是:

$5$ $279$
$7$ $279$

则按输出错误处理，不能得分。

输入格式

共n+1行。

第 $1$ 行为一个正整数 $n( \le 300)$ ，表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1~n$ （恰好是输入数据的行号减 $1$ ）。

所给的数据都是正确的，不必检验。

//感谢黄小U饮品修正输入格式

输出格式

共5行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, y, z;
pair<pair<int, int>, int> a[320];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &x, &y, &z);
		a[i].first.first = x + y + z;
		a[i].first.second = x;
		a[i].second = -i;
	}
	sort(a, a + n);
	reverse(a, a + n);
	for (int i = 0; i < 5; i++) {
		printf("%d %d\n", -a[i].second + 1, a[i].first.first);
	}
	return 0;
}

题解

模拟排序

P1626 象棋比赛

https://www.luogu.com.cn/problem/P1626

题目描述

有N个人要参加国际象棋比赛，该比赛要进行K场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。

在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望K场对弈中双方的等级差的总和最小。

比如有7个选手，他们的等级分别是30，17，26，41，19，38，18，要进行3场比赛。最好的安排是选手2对选手7，选手7对选手5，选手6对选手4。此时等级差的总和等于（18-17）+（19-18）+（41-38）=5达到最小。

输入格式

第一行两个正整数N，K

接下来有N行，第i行表示第i-1个人等级。

[数据规模]

在90%的数据中，1≤N≤3000；

在100%的数据中，1≤N≤100000；

保证所有输入数据中等级的值小于100000000，1≤K≤N-1。

输出格式

在第一行输出最小的等级差的总和。

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[100020];
int n, m, s;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n - 1; i++) {
		a[i] = a[i + 1] - a[i];
	}
	sort(a, a + n - 1);
	for (int i = 0; i < m; i++) {
		s += a[i];
	}
	printf("%d\n", s);
	return 0;
}

题解

模拟排序

P4829 kry loves 2048

https://www.luogu.com.cn/problem/P4829

题目背景

kls是一个人赢。

题目描述

kls最近在玩一款类似2048的游戏，规则是这样的：

一开始，有 $n$ 个方块，每个方块上有一个 $1$ 到 $m$ 的整数。

kls可以进行两种操作：

选择两个数字相同的方块（不一定要相邻），将它们合并成一个数字为原来的两倍的方块；
减小一个方块上的数字。

操作的次数没有限制，最终的得分为所有方块上的最大的数字。

因为kls要去陪妹子了，没有时间继续玩，他想让你帮忙计算一下，最多能得到多少分。

输入格式

因为数据可能很大，读入容易超时，所以kls给你们提供了一个c++的随机数生成器。

void generate_array(int a[], int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i] = x % m + 1;
    }
}

把这个函数复制到你的程序里。用一个足够大的数组，以及输入数据给出的 $n$ ， $m$ 和 $seed$ 作为参数，调用这个函数。然后这个数组里就是一开始的方块上的数字（下标从0开始）。

输入一行三个数 $n,m,seed$ ，含义如上。

输出格式

一行一个数，表示最大得分。

样例 #1

样例输入 #1

5 10 233

样例输出 #1

样例 #2

样例输入 #2

5 50 3

样例输出 #2

样例 #3

样例输入 #3

1000 1000 666

样例输出 #3

提示

样例解释

样例1生成出来的数是 6 10 7 5 4。

样例2生成出来的数是 8 12 48 4 4。

数据范围

对于30%的数据， $n, m \le 10$ ；

对于60%的数据， $n, m \le 10^5$ ；

对于100%的数据， $n, m \le 10^7$ ， $1 \le seed \le 10^9$ 。

参考代码

题解

用堆/队列贪心，类似合并果子

P3918 [国家集训队]特技飞行

https://www.luogu.com.cn/problem/P3918

题目背景

wqs 爱好模拟飞行。
clj 开了一家神犇航空，由于 clj 还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符

题目描述

神犇航空开展了一项载客特技飞行业务。每次飞行长 $n$ 个单位时间，每个单位时间可以进行一项特技动作，可选的动作有 $k$ 种，每种动作有一个刺激程度 $c_i$ 。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间) $\times c_i$ ，若为第一次进行该动作，价值为 $0$ 。安排一种方案，使得总价值最大。

输入格式

第一行，两个整数， $n$ 和 $k$ ，如上所述；

第二行， $k$ 个整数，表示 $k$ 种动作的 $c_i$ 值。

输出格式

仅一行，一个整数，表示最大总价值。

样例 #1

样例输入 #1

5 2
2 2

样例输出 #1

提示

数据规模与约定

对于 $10\%$ 的测试数据， $n \le 20$ ， $k \le 3$ 。
对于 $100\%$ 的测试数据， $1 \le n \le 10^3$ ， $1 \le k \le 300$ ， $0 \le c_i \le 10^3$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, z;
int a[10020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a + m);
	n--;
	for (int i = m - 1; i >= 0 && n > 0; i--)
	{
		z += n * a[i];
		n -= 2;
	}
	printf("%d\n", z);
	return 0;
}

题解

排序，最大的放两边

P2969 [USACO09DEC]Music Notes S

https://www.luogu.com.cn/problem/P2969

题目描述

FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for B_i (1 <= B_i <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B_1, note 2 from time B_1 through just before time B_1 + B_2, etc.

However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, 'In the interval from time T through just before time T+1, which note should you be playing?' The cows need your help to answer these questions which are supplied as T_i (0 <= T_i <=

end_of_song).

Consider this song with three notes of durations 2, 1, and 3 beats:

Beat:   0    1    2    3    4    5    6    ...
        |----|----|----|----|----|----|--- ...
        1111111111     :              :
                  22222:              :
                       333333333333333:

Here is a set of five queries along with the resulting answer:

Query Note

2 2

3 3

4 3

0 1

1 1

约翰准备教他的奶牛们弹一首歌.这首歌由N(1<=n<= 50000)个音阶组成，第i个音阶要敲击Bi<=10000次.奶牛从第0时刻开始弹，因此他从0时刻到Bi-1时刻都是敲第1个音阶，然后他从B1时刻到B1+B2-1时刻敲第2个音阶，从B1+B2到B1+B2+B3-1时刻敲第3个音阶……现在有q(i<q<50000)个问题：在时间段区间t,T+1内，奶牛敲的是哪个音阶？

输入格式

* Line 1: Two space-separated integers: N and Q

* Lines 2..N+1: Line i+1 contains the single integer: B_i

* Lines N+2..N+Q+1: Line N+i+1 contains a single integer: T_i

输出格式

* Lines 1..Q: For each query, print a single integer that is the index of the note that the cows should be playing.

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

排序二分
1 1 2 3 3 3

前缀和，二分
2 1 3

2 3 6
2. 排序所有询问，扫一遍

while (还有询问)
while (这一段在询问之前)
过掉
回答这个询问

P1271 【深基9.例1】选举学生会

https://www.luogu.com.cn/problem/P1271

题目描述

学校正在选举学生会成员，有 $n(n\le 999)$ 名候选人，每名候选人编号分别从 1 到 $n$ ，现在收集到了 $m(m<=2000000)$ 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

样例输出 #1

1 2 2 2 2 2 2 2 5 5

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, c[1000];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &x);
		c[x]++;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < c[i]; j++)
		{
			printf("%d ", i);
		}
	}
	printf("\n");
	return 0;
}

题解

计数排序

vector b[1000];
for (int i = 0; i < m; i++)
{
cin >> x >> name;
b[x].push_back(name);
}

P4378 [USACO18OPEN]Out of Sorts S

https://www.luogu.com.cn/problem/P4378

题目描述

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie的对长度为 $N$ 的数组 $A$ 进行排序的奶牛码实现。

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

给定一个输入数组，请预测Bessie的代码会输出多少次“moo”。

输入格式

输入的第一行包含 $N$ （ $1 \leq N \leq 100,000$ ）。接下来 $N$ 行描述了 $A[0] \ldots A[N-1]$ ，每个数都是一个范围为 $0 \ldots 10^9$ 的整数。输入数据不保证各不相同。

输出格式

输出“moo”被输出的次数。

样例 #1

样例输入 #1

样例输出 #1

提示

供题：Brian Dean

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z;
int a[100020];
int r[100020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		r[i] = i;
	}
	stable_sort(r, r + n, [](int x, int y){return a[x] < a[y];});
	for (int i = 0; i < n; i++) {
		z = max(z, r[i] - i);
	}
	printf("%d\n", z + 1);
	return 0;
}

题解

pair 带下标排序，排序

P4375 [USACO18OPEN]Out of Sorts G

https://www.luogu.com.cn/problem/P4375

题目描述

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie最初的对长度为 $N$ 的数组 $A$ 进行排序的奶牛码实现。

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

在用若干个数组测试了她的代码之后，Bessie得到一个有趣的观察现象：大的元素很快就会被拉到数组末尾，然而小的元素需要很长时间“冒泡”到数组的开头（她怀疑这就是为什么这个算法得名的原因）。为了实验和缓解这一问题，Bessie试着修改了她的代码，使代码在每次循环中向前再向后各扫描一次，从而无论是大的元素还是小的元素在每一次循环中都有机会被拉较长的一段距离。她的代码现在是这样的：

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

给定一个输入数组，请预测Bessie修改后的代码会输出多少次“moo”。

输入格式

输出格式

输出“moo”被输出的次数。

样例 #1

样例输入 #1

样例输出 #1

提示

供题：Brian Dean

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
bool v[100020];
int n, c, z = 1;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		if (a[i].second > i)
		{
			c++;
		}
		if (v[i])
		{
			c--;
		}
		v[a[i].second] = true;
		z = max(z, c);
	}
	cout << z << endl;
	return 0;
}

题解

pair 带下标排序，排序

P6033 [NOIP2004 提高组] 合并果子加强版

https://www.luogu.com.cn/problem/P6033

题目背景

本题除【数据范围与约定】外与 P1090 完全一致。

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $(n - 1)$ 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 堆果子，数目依次为 $1,~2,~9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力为 $3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

输入的第一行是一个整数 $n$ ，代表果子的堆数。
输入的第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 堆果子的个数 $a_i$ 。

输出格式

输出一行一个整数，表示最小耗费的体力值。

样例 #1

样例输入 #1

3 
1 2 9

样例输出 #1

提示

【数据规模与约定】

本题采用多测试点捆绑测试，共有四个子任务。

Subtask 1（10 points）： $1 \leq n \leq 8$ 。
Subtask 2（20 points）： $1 \leq n \leq 10^3$ 。
Subtask 3（30 points）： $1 \leq n \leq 10^5$ 。
Subtask 4（40 points）： $1 \leq n \leq 10^7$ 。

对于全部的测试点，保证 $1 \leq a_i \leq 10^5$ 。

【提示】

请注意常数因子对程序效率造成的影响。
请使用类型合适的变量来存储本题的结果。
本题输入规模较大，请注意数据读入对程序效率造成的影响。

参考代码

#include <bits/stdc++.h>
using namespace std;
int get()
{
	char c;
	while (!isdigit(c = getchar()))
	{
	}
	int x = c - '0';
	while (isdigit(c = getchar()))
	{
		x = x * 10 + c - '0';
	}
	return x;
}
int c[100020];
long long q1[10000020];
long long q2[10000020];
int b1, f1, b2, f2;
long long pop()
{
	if (b2 == f2 || (b1 < f1 && q1[b1] < q2[b2]))
	{
		return q1[b1++];
	}
	else
	{
		return q2[b2++];
	}
}
int main()
{
	int n = get();
	for (int i = 0; i < n; i++)
	{
		c[get()]++;
	}
	for (int i = 1; i <= 100000; i++)
	{
		while (c[i]--)
		{
			q1[f1++] = i;
		}
	}
	long long z = 0;
	for (int i = 1; i < n; i++)
	{
		long long x = pop();
		long long y = pop();
		z += x + y;
		q2[f2++] = x + y;
	}
	cout << z << endl;
	return 0;
}

题解

P2205 [USACO13JAN]Painting the Fence S

https://www.luogu.com.cn/problem/P2205

题目描述

Farmer John has devised a brilliant method to paint the long fence next to his barn (think of the fence as a one-dimensional number line). He simply attaches a paint brush to his favorite cow Bessie, and then retires to drink a cold glass of water as Bessie walks back and forth across the fence, applying paint to any segment of the fence that she walks past.

Bessie starts at position 0 on the fence and follows a sequence of N moves (1 <= N <= 100,000). Example moves might be "10 L", meaning Bessie moves 10 units to the left, or "15 R", meaning Bessie moves 15 units to the right. Given a list of all of Bessie's moves, FJ would like to know what area of the fence gets painted with at least K coats of paint. Bessie will move at most 1,000,000,000 units away from the origin during her walk.

Farmer John 想出了一个给牛棚旁的长围墙涂色的好方法。（为了简单起见，我们把围墙看做一维的数轴，每一个单位长度代表一块栅栏）

他只是简单的把刷子蘸满颜料，系在他最喜欢的奶牛Bessie上，然后让Bessie来回地经过围墙，自己则在一旁喝一杯冰镇的凉水。（……-_-|||)

Bessie 经过的所有围墙都会被涂上一层颜料。Bessie从围墙上的位置0出发，并将会进行N次移动(1 <= N <= 100,000)。比如说，“10 L”的意思就是Bessie向左移动了10个单位。再比如说“15 R”的意思就是Bessie向右移动了15个单位。

给出一系列Bessie移动的清单。FJ 想知道有多少块栅栏涂上了至少K层涂料。注意：Bessie最多会移动到离原点1,000,000,000单位远的地方。

输入格式

* 第1行：两个整数： N K

* 第2...N+1 行：每一行都描述了Bessie的一次移动。（比如说 “15 L"）

输出格式

* 一个整数：被至少涂上K层涂料的栅栏数

（注意：输出的最后一定要输出换行符！否则会WA）

样例 #1

样例输入 #1

样例输出 #1

提示

PS1：来源：usaco jan silver P01 想看原题的请戳http://www.usaco.org/index.php?page=viewproblem2&cpid=226）

PS2：测试数据也可以在在http://www.usaco.org/index.php?page=jan13problems上下载，还可以看到题解（不过是英文的:-D）

PS3:如果有翻译的问题或题目的不理解，可以在问答后面留言的说。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, p, c, z;
char o;
pair<int, int> a[200020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d %c", &x, &o);
		if (o == 'L')
		{
			a[i] = make_pair(p - x, +1);
			a[i + n] = make_pair(p, -1);
			p -= x;
		}
		else
		{
			a[i] = make_pair(p + x, -1);
			a[i + n] = make_pair(p, +1);
			p += x;
		}
	}
	sort(a, a + 2 * n);
	for (int i = 0; i + 1 < 2 * n; i++)
	{
		c += a[i].second;
		if (c >= m)
		{
			z += a[i + 1].first - a[i].first;
		}
	}
	printf("%d\n", z);
	return 0;
}