排序和RMQ

排序

1. 七夕祭

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;
}

2.糖果传递

122. 糖果传递 - AcWing题库

这题就是上一题的简单版 只有行

#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;
}

3.动态中位数（经典题型）

106. 动态中位数 - AcWing题库


 

对顶堆的应用

对顶堆是由一个大顶堆和一个小顶堆组合而成的数据结构，与传统堆维护最大数不同，对顶堆用于动态维护第k大的数。在对顶堆中，小根堆位于大根堆的上方，要保证小根堆的所有数始终比大根堆大。

答案就是大根堆的堆顶

#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题库

问逆序对个数 学校oj有一道一模一样的 这

直接归并排序就好了

#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;
}

一年前写的代码

#include 
using namespace std;
const int N=1e6+10;
int a[N],b[N];
long long cnt=0;
void merge_sort(int a[],int b[],int l,int mid,int r)
{
    int lpos=l,rpos=mid+1,pos=l;
    while(lpos<=mid&&rpos<=r)
    {
        if(a[lpos]<=a[rpos]) b[pos++]=a[lpos++];
        else b[pos++]=a[rpos++],cnt+=mid-lpos+1;
    }
    while(lpos<=mid) b[pos++]=a[lpos++];
    while(rpos<=r) b[pos++]=a[rpos++];
    while(l<=r) a[l]=b[l],l++;
}
void merge_(int a[],int b[],int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    merge_(a,b,l,mid);
    merge_(a,b,mid+1,r);
    merge_sort(a,b,l,mid,r);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        {
            break;
        }
        cnt=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i
        {
            scanf("%d",&a[i]);
        }
        merge_(a,b,0,n-1);
        printf("%lld\n",cnt);
    }
    return 0;
}

RMQ（st表）（跳表）

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

1.天才的记忆

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;
}