现给你一个长度为 $n$的序列 $a_1,\cdots ,a_n$​和 $m$个互不相同的整数 $b_1,\cdots ,b_m$​。你需要按照这 $m$个数对序列 $a$进行狠狠地切割。

具体的，对于一个数字 $i\in [1,n]$，如果存在一个整数 $j\in [1,m]$，使得 $a_i=b_j$，则将位置 $i$称为一个切割点。对序列 $a$中的每一个切割点，我们在这个位置进行一次狠狠地切割。方法是，将该位置的数字去除，然后在这个位置将其左右的序列/片段一分两半。

如果对狠狠地切割的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算，在进行了所有可能的狠狠地切割后，序列被切割为了多少片段。

特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做片段。同样的，如果 $1$或 $n$为切割点，其与开头和结尾之间也不存在片段。

如果对片段的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。

【输入格式】

第一行为两个整数，依次表示序列 $a$的长度 $n$和序列 $b$的长度 $m$。
第二行有 $n$个整数，第 $i$个整数表示 $a_i$。
第三行有 $m$个整数，第 $i$个整数表示 $b_i$。

【输出格式】

输出一个整数，代表狠狠地切割后的片段的个数。

【输入输出样例#1】

输入#1

6 2
3 4 3 5 2 6
5 4

输出#1

3

【输入输出样例#2】

输入#2

6 3
3 4 3 5 2 6
3 5 6

输出#2

2

【说明提示】

样例 1 解释

在狠狠地切割前，序列 $a$a

如下所示：$\begin{array}{cccccc}3& 4& 3& 5& 2& 6\end{array}$

​$\begin{array}{cccccc}3& \mathrm{\mid }& 3& \mathrm{\mid }& 2& 6\end{array}$

​$\begin{array}{ccccc}\stackrel{\text{片段 1}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 3}}{\overbrace{26}}\end{array}$

样例 2 解释

以下我们展示去除之后的序列：

$\begin{array}{cccccc}\mathrm{\mid }& 4& \mathrm{\mid }& \mathrm{\mid }& 2& \mathrm{\mid }\end{array}$

​$\begin{array}{ccccccc}\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\mathrm{\mid }& \stackrel{\text{片段 1}}{\overbrace{4}}& \mathrm{\mid }& \stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{2}}& \mathrm{\mid }\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\end{array}$​

数据规模与约定

• 对于 $30\mathrm{\%}$的数据，保证 $a$序列中没有任何元素在 $b$中出现过。形式化的，$\mathrm{\forall }i\in [1,n],\mathrm{\forall }j\in [1,m],a_i\mathrm{\ne }{b}_j$。
• 对于 $100\mathrm{\%}$的数据，保证 $1\le n,m\le 5\times 10^5$，$-10^{18}\le a_i,b_i\le 10^{18}$，序列 $b$中的元素两两不同。

提示

本题输入规模较大，建议考虑使用较快的读入读出方式。

【解题思路】

先将$b$序列排序，便于后续查找。然后遍历 $a$序列,通过二分查找法判断是否在$b$序列中。存在即分割，循环计数

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 * 1e5 + 5;
long long a[MAXN];
long long b[MAXN];
int n, m;

bool isdivide(long long x) {
	auto i = lower_bound(b + 1, b + m + 1, x) - b;
	if (x == b[i]) {
		return true;
	} else {
		return false;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	sort(b + 1, b + m + 1); //排序
	int t = 0;
	int cnt = 0; //计数
	for (int i = 1; i <= n; i++) {
		if (isdivide(a[i])) {
			if (t > 0) {
				cnt++;
				t = 0;
			}
		} else {
			t++;
		}
	}
	if (t > 0) {
		cnt++;
	}
	cout << cnt << endl;

}

题目描述

给定长度为N的数列A = (A₁, A₂, …, A_N)， 和 整数K = 0, 1, 2, …, N−1，请问 A 中有多少个A_i （1 <= i <= n) 恰好包含 k 个大于它的不同正整数。

【输入格式】

共两行，
第一行，一个正整数 N，表示输入数的个数；
第二行，N个整数 A_i 。

【输出格式】

共N行，每行一个整数，分别表示K = 0, 1, 2, …, N−1时的答案。

【输入输出样例#1】

输入#1

6
2 7 1 8 2 8

输出#1

2
1
2
1
0
0

【输入输出样例#2】

输入#2

1
1

输出#2

1

【输入输出样例#3】

输入#3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

输出#3

2
1
2
1
2
1
1
0
0
0

【说明提示】

对于样例1的说明：
当 K 为 2 时.
A₁ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₂ = 7，A包含了 1 个不同的大于它的正整数：8；
A₃ = 1，A包含了 3 个不同的大于它的正整数：2、7、8；
A₄ = 8，A包含了 0 个不同的大于它的正整数：无；
A₅ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₆ = 8，A包含了 0 个不同的大于它的正整数：无；
​

【数据范围】

1 ≤ N ≤ 2 × 10⁵

1 ≤ A_i ≤ 10⁹

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;
int n;
int a[MAXN];
int b[MAXN];
int k[MAXN];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1); //排序
	//去重
	int j = 1;
	b[j] = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] != b[j]) {
			j++;
			b[j] = a[i];
		}
	}
	for (int i = 1; i <= n; i++) {
		int x = upper_bound(b + 1, b + j + 1, a[i]) - b;
		k[j - x + 1]++;
	}
	for (int i = 0; i < n; i++) {
		cout << k[i] << endl;
	}


}

题目描述

现有 m 所学校，每所学校预计分数线是 $a_i$​。有 n 位学生，估分分别为 $b_i$。

根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（分数线可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

【输入格式】

第一行读入两个整数 m,n。m 表示学校数，n 表示学生数。
第二行共有 m 个数，表示 m 个学校的预计录取分数。第三行有 n 个数，表示 n 个学生的估分成绩。

【输出格式】

输出一行，为最小的不满意度之和。

【输入输出样例#1】

输入#1

复制

4 3
513 598 567 689
500 600 550

输出#1

复制

32

【数据范围】

对于 80% 的数据，1 <= n,m <= 10000，估分和录取线 <= 1000000；
对于 100% 的数据，1 <= n,m <= 200000，估分和录取线 <= 1000000；

【代码样例】

#include <bits/stdc++.h>
using namespace std;
long long  m,n,cnt;
int a[200005],b[200005];
int main(){   
    cin>>m>>n;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a+1,a+m+1);
    //sort(b+1,b+n+1);
     
    for(int i=1;i<=n;i++){
    	auto x=lower_bound(a+1,a+m+1,b[i])-a;
    	if(x==m+1) {
    		cnt+=abs(b[i]-a[m]);
    	} else if(x!=1) {
    		cnt+=min(abs(b[i]-a[x]),abs(b[i]-a[x-1]));
    	} else {
    		cnt=abs(b[i]-a[x]);	
    	}
    }
    cout<<cnt<<endl;
    return 0;
}

【题目描述】

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_n$​。

请你找到数组中只出现过一次的数当中最小的那个数。

输出找到的数的索引编号。

$a_1$​ 的索引编号为 $1$，$a_2$​ 的索引编号为 $2$，…，$a_n$ 的索引编号为 $n$。

【输入格式】

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_n$​。

【输出格式】

每组数据输出一行结果，即满足条件的数的索引编号，如果不存在满足条件的数，则输出 $\text{−}1$。

【输入输出样例#1】

输入#1

2
2
1 1
3
2 1 3

输出#1

-1
2

【输入输出样例#2】

输入#2

4
4
2 2 2 3
1
1
5
2 3 2 4 2
6
1 1 5 5 4 4

输出#2

4
1
2
-1

【输入输出样例#3】

输入#3

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

输出#3

2
4
4

【数据范围】

$1\le T\le 2\times 10^4,$

$1\le n\le 2\times 10^5,$

$1\le a_i\le n,$

$\text{同一测试点内的所有}n\text{的和不超过}2\times 10^5$

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;

struct m {
	int i;
	int num;
} a[MAXN];

bool cmp(m x, m y) {
	return x.i < y.i;
}

int main() {
	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i].i;
			a[i].num = i;
		}
		sort(a + 1, a + n + 1, cmp);
		int cnt = 1;
		m x = a[1];
		if (n == 1) {
			cout << 1 << endl;
		} else {
			for (int i = 2; i <= n; i++) {
				if (x.i == a[i].i) {
					cnt++;
					if (i == n) {
						cout << -1 << endl;
					}
				} else {
					if (cnt > 1) {
						x = a[i];
						cnt = 1;
						if (i == n) {
							cout << x.num << endl;
							break;
						}
					} else {
						cout << x.num << endl;
						break;
					}
				}
			}
		}

	}

}

 题目描述

虽然 Miss Medusa 到了北京，领了科技创新奖，但是她还是觉得不满意。原因是：他发现很多人都和她一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

【输入格式】

第一行两个整数 $n,m$，表示有 $n$ 个人获得科技创新奖，$m$ 个人获得特殊贡献奖。

第二行 $n$ 个正整数，表示获得科技创新奖的人的编号。

第三行 $m$ 个正整数，表示获得特殊贡献奖的人的编号。

【输出格式】

输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

【输入输出样例#1】

输入#1

复制

4 3
2 15 6 8
8 9 2

输出#1

复制

2 8

【数据范围】

对于 $50\mathrm{\%}$ 的数据，$0\le n,m\le 1000$，获得奖项的人的编号 $<2\times 10^9$；

对于 $100\mathrm{\%}$ 的数据，$0\le n,m\le 10^6$，获得奖项的人的编号 $<2\times 10^{18}$。

输入数据保证第二行任意两个数不同，第三行任意两个数不同。

【代码样例】

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long a1[1000005],a2[1000005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a1[i];
	for(int i=1;i<=m;i++) cin>>a2[i];
	sort(a2+1,a2+m+1);
	//sort(a1+1,a1+n+1);
	for(int i=1;i<=n;i++){
		if(a1[i]==a2[lower_bound(a2+1,a2+m+1,a1[i])-a2]){
			cout<<a1[i]<<" ";
		}
	}
}

【题目描述】

Farmer John 正再一次尝试给他的 $N$ 头奶牛拍照（$2\le N\le 1000$）。

每头奶牛有一个范围在 $1\dots 100$ 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。

Farmer John 可以分成的最大组数是多少？

【输入格式】

输入的第一行包含 N。下一行包含 N 个空格分隔的整数，为 N 头奶牛的品种编号。

【输出格式】

输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。

【输入输出样例#1】

输入#1	输出#1
7 1 3 5 7 9 11 13	3

【输入输出样例#2】

输入#2	输出#2
7 8 2 16 12 1 15 4	5

【输入输出样例#3】

输入#3	输出#3
6 1 2 3 4 5 6	6

【说明提示】

样例1解释，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。

【代码样例】

#include <bits/stdc++.h>
using namespace std;

int main() {
	int odd = 0, even = 0; //奇数、偶数
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (x % 2 == 0) {
			even++;
		} else {
			odd++;
		}
	}
	if (odd < even) {
		cout << 2 * odd + 1 << endl;
	} else if (odd >= even) {
		if ((odd - even) % 3 == 0) {
			cout << 2 * (even + (odd - even) / 3) << endl;
		} else if ((odd - even) % 3 == 1) {
			cout << 2 * (even + (odd - even) / 3) - 1 << endl;
		} else if ((odd - even) % 3 == 2) {
			cout << 2 * (even + (odd - even) / 3) + 1 << endl;
		}
	}
}