10分求助（二分，6个TLE，其他WA）

P1678 烦恼的高考志愿

Your_Majesty @ 2023-01-20 13:05:07


#include<iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int a[100010],b[100010];
int main(){
    int m,n,sum=0,ans=0,mid,l,r;
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }

    for(int i=1;i<n;i++){
        ans=0;
        for(int j=1;j<=n-i;j++){
            if(a[j]>a[j+1]){
                sum=a[j];
                a[j]=a[j+1];
                a[j+1]=sum;
                ans++;
            }
        }
        if(ans==0) break;
    }
    ans=0;

    for(int i=1;i<=n;i++){
        l=0;
        r=n+1;
        while(l<r){
            mid=l+(r-l)/2;
            if(a[mid]<=b[i]) l=mid+1;
            if(a[mid]>b[i]) r=mid;
        }
//      if(a[l]-b[i]>a[l-1]-b[i]) ans+=a[l-1]-b[i];
//      else ans+=a[l]-b[i];
        ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));
    }
    cout<<ans;
    return 0;
}

by hqc111 @ 2023-01-20 13:26:10

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,m;
int bs(int x){
    int l=0,r=n+1;
    while(l+1<r){
          int mid=(l+r)/2;
          if(a[mid]>x) r=mid;
          else l=mid;
    }
    return min(x-a[l],a[r]-x);   
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    sort(a+1,a+n+1);
    a[0]=-0x3f3f3f3f,a[n+1]=0x3f3f3f3f;//哨兵防越界
    long long sum=0;
    for(int i=1;i<=m;i++){
        int num;cin>>num;
        sum+=bs(num); 
    }
    cout<<sum<<endl;
}

by hqc111 @ 2023-01-20 13:27:31

加上哨兵应该就能解决TLE了

|