conttyhello @ 2024-11-09 16:13:26
题目：P1678 烦恼的高考志愿 请看代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int a[100100],b[100100];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
for(int i=1; i<=m; i++)
{
cin>>b[i];
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1; i<=m; i++)
{
int l=0,r=n+1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]<=b[i])
{
l=mid+1;
}
else
{
r=mid;
}
}
if(b[i]<=a[1])
{
ans+=a[1]-b[i];
}
else
{
ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));}
}
cout<<ans;
return 0;}明明已经100分了，可是显示的是未通过的状态。不管怎么改，一直告诉我有一个错误，到底错在哪？
by djkarry @ 2024-11-09 17:13:57
那个错误的地方的输入数据：\ 1 100000\ 1000000\ 其余全是0\ 输出：100000000000\ 直接特判就行
by conttyhello @ 2024-11-10 16:28:53
……
by conttyhello @ 2024-11-10 16:29:11
没听懂……
by conttyhello @ 2024-11-10 16:31:02
哪位大佬可以细讲一下
by hlb44 @ 2024-11-13 21:21:14
从样例数据分析中，我们可以看出，本题的核心就是根据每个学生的分数，找出比这个分数小的录取分数的最大值和比这个分数大的录取分数的最小值。既然是查找问题，我们肯定可以使用二分查找来实现，二分查找的时间复杂度为 O(logn)。最多的数据为 1e5 个，因此可以满足。
1、读入数据。
2、对高校录取分数进行排序。
3、应该是没有必要进行出重，当然去重也是可以的。
4、对每个学生高考分数，在录取分数中查找左下界和右上界。
5、如果左下界不等于右上界，说明高考分数和某个学校的录取分数相同。也就意味着这个学生的不满度为 0。
6、如果左下界等于右上界，说明学生高考分数在两个高校录取分数之间。需要分类讨论。分布右三种情况：一是小于高校录取分数最小值，这个时候 lo=hi=0，那么不满值应该是（高校录取分数最小值 - 高考分数）；二是大于高校录取分数最大值，这个时候 lo=hi=m，那么不满值应该是（高考分数 - 高校录取分数最大值）；三是在两个高校录取分数线之间，那么不满足应该右有两个，即（高考分数 - 高校录取分数[lo-1]）和（高校录取分数[hi] - 高考分数），我们取最小值即可。
代码：
/*
OJ：luogu
题目：P1678 烦恼的高考志愿
地址：https://www.luogu.com.cn/problem/P1678
*/
#include <bits/stdc++.h>
const int MAXM = 1e5+2;
int a[MAXM];//学校分数
const int MAXN = 1e5+2;
int b[MAXM];//学生分数
int main() {
int n, m;
scanf("%d%d", &m, &n);
int i;
//读入学校分数
for (i=0; i<m; i++) {
scanf("%d", &a[i]);
}
//读入学生分数
for (i=0; i<n; i++) {
scanf("%d", &b[i]);
}
std::sort(a, a+m);//排序
//统计
unsigned long long ans = 0;
for (i=0; i<n; i++) {
int lo = std::lower_bound(a, a+m, b[i]) - a;
int hi = std::upper_bound(a, a+m, b[i]) - a;
if (lo==hi) {
//b[i]没有在a[i]中，找最小的
if (0==lo) {
ans += (a[lo]-b[i]);
} else if (hi>=m) {
ans += (b[i]-a[hi-1]);
} else {
ans += std::min(b[i]-a[lo-1], a[hi]-b[i]);
}
}
}
printf("%llu\n", ans);
return 0;
}by hlb44 @ 2024-11-13 21:22:22
@conttyhello 哦哦哦，这是c++啊，我给你改一下哈
by hlb44 @ 2024-11-13 21:26:16
代码:
/*
OJ：luogu
题目：P1678 烦恼的高考志愿
地址：https://www.luogu.com.cn/problem/P1678
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e5+2;
int a[MAXM],b[MAXM];
int main() {
int n, m;
cin>>m>>n;
for (int i=0; i<m; i++) cin>>a[i];
for (int i=0; i<n; i++) cin>>b[i];
sort(a,a+m);
unsigned long long ans=0;
for (int i=0; i<n; i++) {
int lo=lower_bound(a,a+m,b[i])-a;
int hi=upper_bound(a,a+m,b[i])-a;
if (lo==hi) {
if(0==lo) ans+=(a[lo]-b[i]);
else if(hi>=m) ans+=(b[i]-a[hi-1]);
else ans+=min(b[i]-a[lo-1],a[hi]-b[i]);
}
}
cout<<ans;
return 0;
}