题解
【基础】最满意的方案
2 条题解
-
0
#include <bits/stdc++.h> using namespace std; int a[100005];//学校分数线 int main(){ int m,n; cin>>m>>n; for(int i=1;i<=m;i++){ cin>>a[i]; } sort(a+1,a+1+m);//学校分数线排序,方便二分查找 long long s=0;//所有学生的不满意度总和 for(int i=1;i<=n;i++){ int x; cin>>x;//当前学生估分 int l=1,r=m; //二分找第一个大于等于x的学校 while(l<=r){ int mid=(l+r)/2; if(a[mid]>=x){ r=mid-1;//mid可能是答案,继续往左找更接近的 }else{ l=mid+1;//分数太低,答案在右边 } } //l是第一个大于等于x的位置 //r是最后一个小于x的位置 if(l==1){//所有学校分数都大于等于估分 s+=a[l]-x; }else if(l==m+1){//所有学校分数都小于估分 s+=x-a[r]; }else{ //答案只可能在x左右两个学校中 s+=min(abs(a[l]-x),abs(a[r]-x)); } } cout<<s; return 0; } -
0
#include<bits/stdc++.h> //895 using namespace std; //定义两个数组,分别储存每个学校的分数线,和每个同学的估分 int a[100100],b[100100]; int main(){ int m,n; 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);//把每个学校的分数线从小到大排序 int ans=0;//答案一开始为0,因为要累加和。 for(int i=1; i<=n; i++){ int l=1,r=m;//定义左边界与右边界 while(l<=r){ int mid=(l+r)/2;//取查找范围的中间值 //如果录取分数线数组中的第mid个元素小于或等于那位同学的分数 if(a[mid]<=b[i]) l=mid+1;//左边界就往右移 else r=mid-1;//右边界就往左移 } if(b[i]<=a[1]) ans += a[1]-b[i];//这里需要特判断一下,不然只能得70分 else ans += min(abs(a[l-1]-b[i]), abs(a[l]-b[i]));//加上两个绝对值中最小 } cout<<ans; return 0; }
- 1