二分法 70分 实在改不动了

yukq11 @ 2023-04-30 16:48:11

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+100;
int n,m;
int stu[maxn];
int sch[maxn];
ll ans=0; 

int main(){
    cin>>m>>n;//n:学生 m:学校
    for(int i = 0; i < m; i++) cin>>sch[i];
    for(int i = 0; i < n; i++) cin>>stu[i];
    sort(sch,sch+m);
    int pos;
    for(int i = 0; i < n; i++){
        pos=lower_bound(sch,sch+m,stu[i])-sch;
        //cout<<pos<<' '<<stu[i]<<' ';
        if(pos==0) ans+=abs(stu[i]-sch[0]);
        else if(pos==n) ans+=abs(stu[i]-sch[n-1]);
        else{
            ans+=min(abs(stu[i]-sch[pos]),abs(stu[i]-sch[pos-1]));
        }
        //cout<<ans<<endl;
    }
    cout<<ans;
    return 0;
}

by uberking @ 2023-05-02 10:45:50

@yukq11 AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int sch[N],stu[N];
LL ans;
int n,m;

//找到第一个学校录取分数大于等于自己的分数 
void solve(int i){
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if( sch[mid]>=stu[i] )  r=mid;
        else l=mid+1;   
    }
    //最小值在 r 或者 r-1 
    ans+=LL(min(sch[r]-stu[i],stu[i]-sch[r-1]));
    return ; 
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)   cin>>sch[i];
    for(int i=1;i<=m;i++)   cin>>stu[i];

    sort(sch+1,sch+n+1);
    sort(stu+1,stu+m+1);

    for(int i=1;i<=m;i++){
        //  1、自己分数是最高的 （随便上）        没学校录取分超过自己 
        //  2、自己分数是最低的 （没学上）        没学校录取分低于自己
        //  2、自己分数夹在中间  （有学上）       有学校录取 
        if(stu[i]>=sch[n])  ans+=LL(stu[i]-sch[n]);
        else if(stu[i]<sch[1])  ans+=LL(sch[1]-stu[i]);
        else solve(i);
    }
    printf("%lld\n",ans);
    return 0;
}

by yukq11 @ 2023-05-04 12:51:02

@uberking 谢谢orz