6.4 二分
6.4.1 102. 最佳牛围栏
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010; int n,F; double a[N],s[N]; bool check(double avg) { for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-avg; double mins=0; for(int k=F;k<=n;k++) { mins=min(mins,s[k-F]); if(s[k]-mins>=0) return true; } return false; } int main() { cin>>n>>F; for(int i=1;i<=n;i++) cin>>a[i]; double l=0,r=2000; while(r-l>1e-5) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } cout<<(int)(r*1000)<<endl; return 0; }
6.4.2 113. 特殊排序
代码：
// Forward declaration of compare API. // bool compare(int a, int b); // return bool means whether a is less than b. class Solution { public: vector<int> specialSort(int N) { vector<int> res(1,1); for(int i=2;i<=N;i++) { int l=0,r=res.size()-1; while(l<r) { int mid=l+r+1>>1; if(compare(res[mid],i)) l=mid; else r=mid-1; } res.push_back(i); for(int j=res.size()-2;j>r;j--) swap(res[j],res[j+1]); if(compare(i,res[r])) swap(res[r],res[r+1]); } return res; } };
6.5 排序
6.5.1 105. 七夕祭
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=100010; int n,m,t; int row[N],col[N],s[N],c[N]; int work(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; for(int i=1;i<=n;i++) c[i]=s[i-1]-(i-1)*avg; sort(c+1,c+n+1); LL res=0; for(int i=1;i<=n;i++) res+=abs(c[i]-c[(n+1)/2]); return res; } int main() { cin>>n>>m>>t; for(int i=0;i<t;i++) { int x,y; cin>>x>>y; row[x]++,col[y]++; } LL r=work(n,row); LL c=work(m,col); if(r!=-1&&c!=-1) cout<<"both "<<r+c<<endl; else if(r!=-1) cout<<"row "<<r<<endl; else if(c!=-1) cout<<"column "<<c<<endl; else cout<<"impossible"<<endl; return 0; }
6.5.2 106. 动态中位数
代码：
// 对顶堆 #include<bits/stdc++.h> using namespace std; const int N=10010; int p,id,m; int ans[N],cnt; int main() { cin>>p; while(p--) { priority_queue<int> down; //大根堆，放较小数，个数比小根堆多一 priority_queue<int,vector<int>,greater<int> > up; //小根堆，放较大数 cnt=1; cin>>id>>m; for(int i=1;i<=m;i++) { int x; cin>>x; if(down.size()==0||down.top()>=x) down.push(x); else up.push(x); if(up.size()>=down.size()) //调整堆元素数量 { down.push(up.top()); up.pop(); } if(up.size()+1<down.size()) //调整堆元素数量 { up.push(down.top()); down.pop(); } if(i%2) ans[cnt++]=down.top(); } cout<<id<<" "<<cnt-1<<endl; for(int i=1;i<cnt;i++) { if(i%10==0) cout<<ans[i]<<endl; else cout<<ans[i]<<" "; } if((cnt-1)%10) cout<<endl; } return 0; } /* 二分插入法 #include<bits/stdc++.h> using namespace std; const int N=10010; int p,id,m; vector<int> a; int ans[N],cnt; //整数二分，得到第一个小于等于x的下标 int get(int x) { int l=0,r=a.size(); while(l<r) { int mid=l+r>>1; if(a[mid]>=x) r=mid; else l=mid+1; } return r; } int main() { cin>>p; while(p--) { a.clear(); a.push_back(-1e9); cnt=1; cin>>id>>m; for(int i=1;i<=m;i++) { int x; cin>>x; if(i==1) a.push_back(x); else { int k=get(x); a.insert(a.begin()+k,x); } if(i%2) ans[cnt++]=a[(i+1)/2]; } cout<<id<<" "<<cnt-1<<endl; for(int i=1;i<cnt;i++) { if(i%10==0) cout<<ans[i]<<endl; else cout<<ans[i]<<" "; } if((cnt-1)%10) cout<<endl; } return 0; } */
6.5.3 107. 超快速排序
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=500010; int n; int a[N],temp[N]; LL merge_sort(int q[],int l,int r) { if(l>=r) return 0; int mid=l+r>>1; LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid&&j<=r) { if(q[i]<=q[j]) temp[k++]=q[i++]; else { res+=mid-i+1; temp[k++]=q[j++]; } } while(i<=mid) { temp[k++]=q[i++]; } while(j<=r) { temp[k++]=q[j++]; } for(i=l,j=0;i<=r;i++,j++) { q[i]=temp[j]; } return res; } int main() { while(true) { cin>>n; if(n==0) break; for(int i=0;i<n;i++) cin>>a[i]; cout<<merge_sort(a,0,n-1)<<endl; } return 0; }
6.6 RMQ
6.6.1 1273. 天才的记忆
代码：
// RMQ解法 #include<bits/stdc++.h> using namespace std; const int N=200010,M=18; int n,m; int w[N]; int f[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]=w[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); return max(f[l][k],f[r-(1<<k)+1][k]); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; init(); cin>>m; while(m--) { int l,r; cin>>l>>r; cout<<query(l,r)<<endl; } return 0; } /*线段树解法 注意INF取值 #include<bits/stdc++.h> using namespace std; const int N=200010,INF=0x3f3f3f3f; int n,m; int w[N]; struct Node { int l,r; int v; // 区间[l, r]中的最大值 Node(){} Node(int _l,int _r,int _v) { l=_l,r=_r,v=_v; } }tr[4*N]; void pushup(int u) // 由子节点的信息，来计算父节点的信息 u表示父节点编号 { tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v); } void build(int u,int l,int r) //u表示父节点编号,从u开始建立[l,r]的线段树 { tr[u]=Node(l,r,w[r]); if(l==r) return; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } int query(int u,int l,int r) { if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了 int mid=tr[u].l+tr[u].r>>1; //注意初值 int v=-INF; if(l<=mid) v=query(u<<1,l,r); if(r>mid) v=max(v,query(u<<1|1,l,r)); return v; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; build(1,1,n); cin>>m; while(m--) { int a,b; cin>>a>>b; cout<<query(1,a,b)<<endl; } return 0; } */
