排序
1.糖果传递
xi是每一个到下一个位置的操作，也即给多少个，可以是负数（意思是反过来给），要使每个位置都相等，则说明每个数都等于平均数，然后把x1当成自由变量，用x1表示其他的xi，然后令S(i-1)-(i-1)*a为ci然后最后相等于变成abs(x1-c1)的和最小值，而这个绝对值的和可以用绝对值不等式|a|+|b|>=|a+b|换，最后证明得x1等于c[n/2]使得这个绝对值的和最小，也即最少的操作
#include<bits/stdc++.h> 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.七夕祭
这题相比上面那题就是多了个列就判断两个方向是否满足即可
#include<bits/stdc++.h> 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.动态中位数
这题用堆顶堆来做，答案就是下面那个堆的堆顶
#include<bits/stdc++.h> 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.超快速排序
这题就是问逆序对的个数，因为假如有个数ai>ai+1，交换后逆序对会减一，则最少的交换次数就等于逆序对的个数，这题用归并排序求逆序对的个数
#include<bits/stdc++.h> 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;i<n;i++) scanf("%d",&a[i]); msort(0,n-1);//跑一遍归并排序 printf("%lld\n",cnt);//输出答案 } return 0; }
RMQ
RMQ也叫ST表和跳表，用来求一个区间的某个性质来用，有数的更改就不能用了
1.天才的记忆
题意就是随便问一段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<bits/stdc++.h> 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<M;j++)//枚举长度 for(int i=1;i+(1<<j)-1<=n;i++)//枚举左边界 if(!j) f[i][j]=a[i]; else f[i][j]=max(f[i][j-1],f[i+(1<<j-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<<k)+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; }
