二分
整数集合上的二分
- 缩小范围时，r=mid,l=mid+1,取中间值时，mid=(l+r)>>1.
- 缩小范围时，l=mid,r=mid-1，取中间值时，mid=(l+r+1)>>1.
原因是第二种如果不使mid的值倾向于r，可能最后会使其产生死循环。
- 因为mid=(l+r)>>2不会取到r值,mid=(l+r+1)>>2不会取到l值，所以我们可以把最初的二分区间[1,n]分别扩大为[1,n+1],和[0,n],如果最终二分终止在这个扩大后的越界下标上，则说明a中不存在所求的数。
实数域上的二分
- 确定好所需要的精度eps，以l+eps<l为循环条件
- 一般需要保留k位小数时，则取eps = 1e-(k+2)
- 有时候精度不容易确定或者表示，就干脆采用循环固定次数的二分方法。
二分答案转化为判定
- 把所求最优解的问题，转化为给定一个值mid，判定是否存在一个可行方案评分达到mid的问题（也是比较常见的问题）
BestCowFences(POJ2018)
题意：给定正整数数列A，求一个平均数最大的，长度不小于L的（连续的）子段
分析：
- 二分枚举平均数，然后通过前缀和一次判断
- 可以通过每一项减去平均数，然后判断是否存在前缀和差大于等于0的情况。
double a[100001],b[100001],sum[100001];int main() { int n,L; cin>>n>>L; for(int i=1;i<=n;i++) scanf("%lf",&a[i]); double l = -1e6,r = 1e6; double eps = 1e-5; while(r-l>eps) { double mid=(l+r)/2; for(int i=1;i<=n;i++) b[i] = a[i] -mid; for(int i=1;i<=n;i++) sum[i] = (sum[i-1]+b[i]); double ans = -1e10; double min_val = 1e10; for(int i=L;i<=n;i++) { min_val = min(min_val,sum[i-L]); ans = max(ans,sum[i]-min_val); } if(ans>0) l = mid; else r = mid; } cout< < 排序
离散化
Cinema(CF670c)
- n个人每个人只会一个语言，m个电影每个电影的语言和字幕采用一种语言。问在语言匹配最多的前提下有可以由多少字幕匹配的情况
int a[200005],b[200005];int main() { int n,m,tmp; map lang; cin>>n; for(int i=0;i >m; for(int i=0;i ans) { ans = lang[a[i]]; index = i; } } for(int i=0;i - 由于语言数量不一定很多，所以直接用map映射储存
中位数
货仓选址
数轴上有N家商店，他们坐标分别为A[1]-A[N]。现在需要在数轴上建立一家货仓，要求使得货仓到每家商店的距离之和最小
货仓需要建在中位数上，把A排序，然后当N为奇数时，货仓建在A[(N+1)/2]，当N为偶数则可以建在A[N/2]-A[N/2+1]之间。
七夕祭（BZOJ3032）
题意不在赘述
分析- 每列之间相互交换不影响每行之间的数
- 每行之间相互交换不影响每列之间的数
- 若计算出行/列平均值，直接减去，最后意味着每一块都是0.
- 因为只能两两交换，所以交换数就是前缀和。
- 但是有一个条件是可以使头尾交换。所以我们要找出一个界限。使得这个前缀和最小。（也就是转换成了环形均匀分配问题）
- 由于S[n]等于0（之前每一项都减去了平均值）.所以找出一个界限k。利用前缀和差我们可以转换成货仓选址问题。
const int N=100010;int x[N],y[N],s1[N],s2[N];int main(){ int n,m,T;scanf("%d%d%d",&n,&m,&T); for(int i=1;i<=T;i++) { int a,b; scanf("%d%d",&a,&b); x[a]++,y[b]++; } if(T%m!=0 && T%n!=0) { printf("impossible\n"); return 0; } for(int i=1;i<=n;i++) x[i]-=T/n; for(int i=1;i<=m;i++) y[i]-=T/m; long long ans=0; if(T%n==0) { for(int i=1;i<=n;i++) s1[i]=s1[i-1]+x[i]; sort(s1+1,s1+n+1); long long k=s1[(n+1)/2]; for(int i=1;i<=n;i++) ans+=abs(k-s1[i]); } if(T%m==0) { for(int i=1;i<=m;i++) s2[i]=s2[i-1]+y[i]; sort(s2+1,s2+m+1); long long k=s2[(m+1)/2]; for(int i=1;i<=m;i++) ans+=abs(k-s2[i]); } if(T%n==0 && T%m==0) printf("both "); else if(T%n==0 && T%m!=0) printf("row "); else printf("column "); printf("%lld\n",ans); return 0;} Running Median(POJ3784)
题意：动态维护中位数问题：依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数
分析：
- 对顶堆：最大堆保存左半部分，最小堆保存有半部分。
- 比ave大的放最小堆，比ave小的放最大堆
- 每次添加后检测两堆大小，如果不等就移动堆顶元素。而这个移动的元素正是现在的中位数。
struct cmp1//最大堆{ bool operator()(int &a,int &b) { return a b; }};int main() { int p; cin>>p; while(p--) { int a[10000]; int k,n; cin>>k>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } priority_queue ,cmp1> ma; priority_queue ,cmp2> mi; cout< <<" "<<(n+1)/2< mi.size()) { ave = ma.top(); mi.push(ave); ma.pop(); } else { ave = mi.top(); ma.push(ave); mi.pop(); } } if(i&1) { if(num==0) cout< 第k大数
- 最朴素的思路就是排序后直接找
- 可以通过快排划分，因为一次划分的结果就是左边的都比标杆小，右边的都比标杆大，可以每次记录右边的数量与k比大小。如果k大就取左边，如果k小就取右边。(复杂度O(n))
逆序对
若i < j,而a[i]>a[j]，则称这一对数为逆序对。
- 可以利用归并排序的归并过程来记录逆序对个数
Ultra-QuickSort（POJ2299）
每次只能交换相邻两数，求排好序需要交换的个数。
- 转换为求逆序对数。因为每次交换就少一对逆序对，所以交换个数也就是逆序对的数量
int a[500005];int n;long long cnt;void merge_sort(int l,int r){ if(l==r) return; int mid = (l+r)/2; //cout< < r||i<=mid&&a[i]<=a[j]) b[m] = a[i++]; else { b[m] = a[j++]; cnt+=mid-i+1; } } //cout< < >n,n) { cnt = 0; for(int i=0;i - 注意cnt要用long long