题目描述

现有 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;
					}
				}
			}
		}

	}

}