Day 3 排序(未完待续)

离散化：

void discrete(){ //离散化
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) 
        if(i==1||a[i]!=a[i-1])
            b[m++]=a[i];
}
int query(int x){ // x映射的为1~m之间的哪一个整数
    return lower_bound(b+1,b+1+n,x)-b; //二分查找
}

• AcWing103 电影
  https://www.acwing.com/problem/content/105/

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200005;
int a[N],b[N],c[N];
int d[3*N],e[3*N],sum[3*N];
int n,m,cnt=1,cntt=1;
void discrete(){
    sort(d+1,d+cnt);
    for(int i=1;i<cnt;i++)
        if(i==1||d[i]!=d[i-1])
            e[cntt++]=d[i];
}
int query(int x){
    return lower_bound(e+1,e+cntt,x)-e;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[cnt++]=a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        d[cnt++]=b[i];
    }
    for(int i=1;i<=m;i++){
        cin>>c[i];
        d[cnt++]=c[i];
    }
    discrete();
    for(int i=1;i<=n;i++){
        int id=query(a[i]);
        sum[id]++;
    }
    int maxb=-1,maxc=-1,ans=0;
    for(int i=1;i<=m;i++){
        int x=query(b[i]);
        int y=query(c[i]);
        if(sum[x]>maxb){
            maxb=sum[x];
            maxc=sum[y];
            ans=i;
        }else{
            if(sum[x]==maxb&&sum[y]>maxc){
                maxb=sum[x];
                maxc=sum[y];
                ans=i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}  

• AcWing104 货仓地址
  https://www.acwing.com/problem/content/106/

  #include<iostream>
  #include<algorithm>
  using namespace std;
  int a[100005];
  int main(){
    int n,zb;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(n%2!=0)
        zb=(n+1)/2;
    else 
        zb=n/2;
    sort(a+1,a+1+n);
    int aa=a[zb];
    for(int i=1;i<=zb;i++)
        a[i]=aa-a[i];
    for(int i=zb+1;i<=n;i++)
        a[i]=a[i]-aa;
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=a[i];
    cout<<ans; 
    return 0;
  }