排序和RMQ

目录

排序 

1.糖果传递

2.七夕祭 

3.动态中位数

 4.超快速排序

RMQ

1.天才的记忆

---

排序 

1.糖果传递

122. 糖果传递 - AcWing题库

 xi是每一个到下一个位置的操作，也即给多少个，可以是负数（意思是反过来给），要使每个位置都相等，则说明每个数都等于平均数，然后把x1当成自由变量，用x1表示其他的xi，然后令S(i-1)-(i-1)*a为ci然后最后相等于变成abs(x1-c1)的和最小值，而这个绝对值的和可以用绝对值不等式|a|+|b|>=|a+b|换，最后证明得x1等于c[n/2]使得这个绝对值的和最小，也即最少的操作

#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int a[N];
ll s[N],c[N];
ll trans(int n,int a[])
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+(ll)a[i];//求前缀和后面用
    if(s[n]%n) return -1;//假如不能均分
    ll avg=s[n]/n;//平均数
    c[1]=0;//第一个是0
    for(int i=2;i<=n;i++) c[i]=s[i-1]-(ll)(i-1)*avg;//图片上有说
    sort(c+1,c+n+1);//排个序
    ll res=0;
    ll cavg;//中位数
    if(n&1) cavg=c[n/2+1];//奇数直接就是中间哪个
    else cavg=(c[n/2]+c[n/2+1])/2;//反之就是中间那两个的中位数
    for(int i=1;i<=n;i++) res+=abs(c[i]-cavg);//答案就是每个数减去中位数
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    ll t=trans(n,a);//将a进行转换
    printf("%lld\n",t);
    return 0;
}

2.七夕祭 

105. 七夕祭 - AcWing题库

这题相比上面那题就是多了个列就判断两个方向是否满足即可

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
int col[N],row[N],s[N];
ll c[N];
ll trans(int n,int a[])
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//求前缀和后面用
    if(s[n]%n) return -1;//假如不能均分
    int avg=s[n]/n;//平均数
    c[1]=0;//第一个是0
    for(int i=2;i<=n;i++) c[i]=s[i-1]-(ll)(i-1)*avg;//图片上有说
    sort(c+1,c+n+1);//排个序
    ll res=0;
    ll cavg;//中位数
    if(n&1) cavg=c[n/2+1];//奇数直接就是中间哪个
    else cavg=(c[n/2]+c[n/2+1])/2;//反之就是中间那两个的中位数
    for(int i=1;i<=n;i++) res+=abs(c[i]-cavg);//答案就是每个数减去中位数
    return res;
}
int main()
{
    int T;
    scanf("%d%d%d",&n,&m,&T);
    int x,y;
    while(T--)
    {
        scanf("%d%d",&x,&y);
        row[x]++,col[y]++;//行跟列这个位置+1个
    }
    ll t1=trans(n,row),t2=trans(m,col);//算一下最小步数
    if(t1!=-1&&t2!=-1) printf("both %lld\n",t1+t2);
    else if(t1!=-1) printf("row %lld\n",t1);
    else if(t2!=-1) printf("column %lld\n",t2);
    else puts("impossible");
    return 0;
}

3.动态中位数

106. 动态中位数 - AcWing题库

这题用堆顶堆来做，答案就是下面那个堆的堆顶

#include
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int p,n,x;
        scanf("%d%d",&p,&n);
        printf("%d %d\n",p,(n+1)/2);
        priority_queue<int> down;//定义一个大根堆
        priority_queue<int,vector<int>,greater<int>> up;//定义一个小根堆
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(down.empty()||x<=down.top()) down.push(x);//假如空或者这个数小于down堆的堆顶元素
            else up.push(x);
            if(down.size()>up.size()+1) up.push(down.top()),down.pop();//假如下面多的上面的数大于1个
            else if(up.size()>=down.size()) down.push(up.top()),up.pop();//假如上面多
            if(i&1)//奇数输出
            {
                printf("%d ",down.top());
                if(++cnt%10==0) puts("");
            }
        }
        if(cnt%10) puts("");
    }
    return 0;
}

 4.超快速排序

107. 超快速排序 - AcWing题库

这题就是问逆序对的个数，因为假如有个数ai>ai+1，交换后逆序对会减一，则最少的交换次数就等于逆序对的个数，这题用归并排序求逆序对的个数

#include
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],temp[N];
ll cnt=0;
void msort(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    msort(l,mid),msort(mid+1,r);//递归出来左右
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)//把左右两边小的存进temp中
        if(a[i]<=a[j]) temp[k++]=a[i++];
        else
        {
            cnt+=mid-i+1;//i~mid这段都比a[j]大，则有mid-i+1个逆序对
            temp[k++]=a[j++];
        }
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];
    for(int i=l,k=0;i<=r;i++,k++) a[i]=temp[k];//把排序好的数给回a
}
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        cnt=0;//置0
        for(int i=0;iscanf("%d",&a[i]);
        msort(0,n-1);//跑一遍归并排序
        printf("%lld\n",cnt);//输出答案
    }
    return 0;
}

RMQ

RMQ也叫ST表和跳表，用来求一个区间的某个性质来用，有数的更改就不能用了

1.天才的记忆

天才的记忆 (nowcoder.com) 

题意就是随便问一段l,r之间的最大值，可以用线段树来做，这题因为没有修改可以用RMQ来做

 询问就是先算出2^k<=r-l+1，求出k，然后答案就是f[l,k]和f[r-2^k-1,k]的最大值，中间虽然有覆盖的区间，但是不影响求最大值，然后求log可以用数学的换地公式来做，因为cmath库中有log函数但是以10为底，我们还可以预处理出来log以2为底的k也行，用的时候直接查表 

#include
using namespace std;
typedef long long ll;
const int N=2e5+10,M=18;
int a[N];
int f[N][M];
int n,m;
void init()
{
    for(int j=0;j//枚举长度
        for(int i=1;i+(1<-1<=n;i++)//枚举左边界
           if(!j) f[i][j]=a[i];
           else f[i][j]=max(f[i][j-1],f[i+(1<-1)][j-1]);//状态转移
}
int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);//获取k
    return max(f[l][k],f[r-(1<1][k]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    init();//预处理RMQ的f函数
    scanf("%d",&m);
    int l,r;
    while(m--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));//输出询问
    }
    return 0;
}