top1编程
← 返回题目
题解

【基础】最满意的方案

2 条题解

  • 0
    @ 2026-7-29 20:22:08
    #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
      @ 2026-7-28 22:10:02
      #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