二分
整数集合上的二分
- 缩小范围时，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<<int(r*1000)<<endl;
return 0;
}
排序
离散化
Cinema(CF670c)
- n个人每个人只会一个语言，m个电影每个电影的语言和字幕采用一种语言。问在语言匹配最多的前提下有可以由多少字幕匹配的情况
int a[200005],b[200005];
int main()
{
int n,m,tmp;
map<int,int> lang;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&tmp);
lang[tmp]++;
}
int ans = 0,index = 0;
cin>>m;
for(int i=0;i<m;i++)
{
scanf("%d",&a[i]);
if(lang[a[i]]>ans)
{
ans = lang[a[i]];
index = i;
}
}
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
for(int i=0;i<m;i++)
{
if(ans == lang[a[i]])
{
if(lang[b[index]]<lang[b[i]])
{
index = i;
}
}
}
cout<<index+1<<endl;
return 0;
}
- 由于语言数量不一定很多，所以直接用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
");
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
",ans);
return 0;
}
Running Median(POJ3784)
题意：动态维护中位数问题：依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数
分析：
- 对顶堆：最大堆保存左半部分，最小堆保存有半部分。
- 比ave大的放最小堆，比ave小的放最大堆
- 每次添加后检测两堆大小，如果不等就移动堆顶元素。而这个移动的元素正是现在的中位数。
struct cmp1//最大堆
{
bool operator()(int &a,int &b)
{
return a<b;
}
};
struct cmp2//最小堆
{
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<int,vector<int>,cmp1> ma;
priority_queue<int,vector<int>,cmp2> mi;
cout<<k<<" "<<(n+1)/2<<endl;
int num = 0,ave = a[0];
for(int i=1;i<=n;i++)
{
if(a[i]<ave)
ma.push(a[i]);
else
mi.push(a[i]);
if(ma.size()!=mi.size())
{
if(ma.size()>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<<ave;
else
cout<<' '<<ave;
//cout<<" "<<ave;
//printf(" %d",ave);
num++;
}
if(num==10)
{
cout<<endl;
num=0;
}
}
if(num!=0)
cout<<endl;
}
return 0;
}
第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<<mid<<endl;
merge_sort(l,mid);
merge_sort(mid+1,r);
int k = r-l+1;
int *b = new int[k];
int i=l,j=mid+1;
for(int m=0;m<k;m++)
{
if(j>r||i<=mid&&a[i]<=a[j])
b[m] = a[i++];
else
{
b[m] = a[j++];
cnt+=mid-i+1;
}
}
//cout<<cnt<<endl;
for(int i=0;i<k;i++)
{
a[i+l] = b[i];
}
delete[] b;
}
int main()
{
while(cin>>n,n)
{
cnt = 0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
merge_sort(0,n-1);
cout<<cnt<<endl;
}
return 0;
}
- 注意cnt要用long long