主要学习了二分算法：
写了一些经典的二分算法；
还写了一些和其他算法结合的二分：
递归分治，
题目：给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求和所有的 h(ai,aj),0<i<j<n;
不能暴力n方，用分治的思想，分解成最小的子问题求两个数的位数差，再层层往上归并，将后半段排序后，枚举前半段每一个数字，对后半段二分查找，可以优化为nlogn的；
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100010];
int b[10] = { 1,10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
int check(int l,int r){
if(l+1 == r)return 0;
int mid = (l+r)/2;
int ans = check(l,mid) + check(mid,r);
sort(a+mid,a+r);
for(int i = l;i < mid; ++i){
for(int j = 1;j <= 9; ++j){
if( b[j] - a[i] > 0 ){
ans += r - (lower_bound(a+mid,a+r,b[j]-a[i])-a);
}
}
}
return ans;
}
signed main()
{
int n;
cin >> n;
for(int i = 1;i <= n; ++i){
cin >> a[i];
}
cout << check(1,n+1) << endl;
return 0;
}
暴力是n3方的二分答案优化为n方logn。check函数是一个n方的求和，用前缀和优化为2*n;
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s;
int w[200010],v[200010];
int l[200010],r[200010];
int a[200010];
int b[200010];
int L = 0,R;
int Y;
int ans = 1e15,sum;
int check(int x){
for(int i = 1;i <= n; ++i){
if( w[i] >= x ){
a[i] = a[i-1] + 1;
b[i] = b[i-1] + v[i];
}
else a[i] = a[i-1],b[i] = b[i-1];
}
Y = 0;
for(int i = 1;i <= m; ++i){
Y += ( a[r[i]] - a[l[i]-1] ) * ( b[r[i]] - b[l[i]-1] );
}
sum = llabs(Y-s);
if( Y > s )return 1;
else return 0;
}
signed main()
{
cin >> n >> m >> s;
for(int i = 1;i <= n; ++i){
cin >> w[i] >> v[i];
R = max(R,w[i]);
}
R+=2;
for(int i = 1;i <= m; ++i){
cin >> l[i] >> r[i];
}
while( L<=R ){
int mid = (L+R)/2;
if( check(mid) ){
L = mid+1;
}
else R = mid-1;
ans = min(ans,sum);
}
cout << ans << endl;
return 0;
}
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000010];//原数组
int b[1000010];//前缀和数组，用来将差分数组还原成原数组
int c[1000010];//差分数组
int d[1000010],l[1000010],r[1000010];
int n,m;
int check(int x){
memset(c,0,sizeof(c));
for(int i = 1;i <= x; ++i){
c[l[i]] += d[i];
c[r[i]+1] -= d[i];
}
for(int i = 1;i <= n; ++i){
b[i] = b[i-1] + c[i];
if( b[i] > a[i] ){
return 0;
}
}
return 1;
}
signed main()
{
cin >> n >> m;
for(int i = 1;i <= n; ++i)cin >> a[i];
for(int i = 1;i <= m; ++i){
cin >> d[i] >> l[i] >> r[i];
}
int l = 1,r = m;
if( check(r) ){
cout << 0 << endl ;
return 0;
}
while( l < r ){
int mid = (l+r)/2;
if( check(mid) ){
l = mid+1;
}
else r = mid;
}
cout << -1 << endl << r << endl ;
return 0;
}
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100010];
int n,k,m;
int check(int x){
int ans = 0;
int num = 0;
int j = 1;
for(int i = 1;i <= n; ++i){
if( a[i] >= x ) num++;
if( num == k ){
ans += n-i+1;
while( a[j] < x ){
ans += n-i+1;
j++;
}
num--;
j++;
}
}
if( ans >= m )return 1;
else return 0;
}
signed main()
{
int T;
cin >> T;
while(T--){
cin >> n >> k >> m;
for(int i = 1;i <= n; ++i){
cin >> a[i];
}
int l = 1,r = 1e9+10;
while( l < r ){
int mid = (l+r)/2;
if( check(mid) ){
l = mid+1;
}
else r= mid;
}
cout << l-1 << endl ;
}
return 0;
}