P1102 A-B 數對
P1102 A-B 數對
暴力枚舉還是很好做的，直接上雙層循環OK
二分思路:查找邊界情況，找出最大下標和最小下標，兩者相減+1即為答案所求
廢話不多說，上代碼
//暴力O(n^3) 72pts
// #include<bits/stdc++.h>
// using namespace std;
// const int N = 1100;
// int a[N],b[N],c[N];// int main()
// {
// int n;cin>>n;
// int cnt = 0;
// for(int i = 1;i <= n;i++)cin>>a[i];
// for(int i = 1;i <= n;i++)cin>>b[i];
// for(int i = 1;i <= n;i++)cin>>c[i];
// for(int i = 1;i <= n;i++)
// {
// for(int j = 1;j <= n;j++)
// {
// for(int z = 1;z <= n;z++)
// {
// if(a[i] < b[j] && b[j] < c[z] ) cnt++;
// }
// }
// }
// cout<<cnt<<"\n";
// return 0;
// }#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll a[N],b[N],c[N];
ll n;
int bs1(int x)
{ll l = -1,r = n+1;while(l+1 != r){ll mid = (l+r)>>1;if(a[mid] < x){l = mid;}else {r = mid;}}if(a[l] < x) return l;return 0;
}
int bs2(int x)
{ll l = -1,r = n+1;while(l+1 != r){ll mid = (l+r)>>1;if(c[mid] <= x){l = mid;}else {r = mid;}}if(c[r] > x) return n-r+1;return 0;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;ll cnt = 0;for(int i = 1;i <= n;i++)cin>>a[i];for(int i = 1;i <= n;i++)cin>>b[i];for(int i = 1;i <= n;i++)cin>>c[i];//因為要二分a[i]和c[i],所以我們需要對其進行排序操作sort(a+1,a+1+n);sort(c+1,c+1+n);for(int i = 1;i <= n;i++){ll x = bs1(b[i]);ll y = bs2(b[i]);cnt += x * y;}cout<<cnt<<"\n";return 0;
}
P8667 [藍橋杯 2018 省 B] 遞增三元組
P8667 [藍橋杯 2018 省 B] 遞增三元組
一開始也是暴力做法，三層for循環拿到手
二分思想:觀察這個式子我們可以看出，b[i] 介于a[i] 和 c[i] 之間，可以選擇枚舉b[i]，再套用二分查找模板查找a[i]中小于b[i]的部分,還有c[i]中大于b[i]的部分
注意:該l,r的取值分別是 -1 和 n+1,因為你的c[i]最終要返回 n-r+1,所以你需要把指針定在n+1上,確保搜索范圍的右邊界在數組外。這樣可以避免數組越界的問題
廢話不多說，上代碼
//暴力O(n^3) 72pts
// #include<bits/stdc++.h>
// using namespace std;
// const int N = 1100;
// int a[N],b[N],c[N];// int main()
// {
// int n;cin>>n;
// int cnt = 0;
// for(int i = 1;i <= n;i++)cin>>a[i];
// for(int i = 1;i <= n;i++)cin>>b[i];
// for(int i = 1;i <= n;i++)cin>>c[i];
// for(int i = 1;i <= n;i++)
// {
// for(int j = 1;j <= n;j++)
// {
// for(int z = 1;z <= n;z++)
// {
// if(a[i] < b[j] && b[j] < c[z] ) cnt++;
// }
// }
// }
// cout<<cnt<<"\n";
// return 0;
// }#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll a[N],b[N],c[N];
ll n;
int bs1(int x)
{ll l = -1,r = n+1;while(l+1 != r){ll mid = (l+r)>>1;if(a[mid] < x){l = mid;}else {r = mid;}}if(a[l] < x) return l;return 0;
}
int bs2(int x)
{ll l = -1,r = n+1;while(l+1 != r){ll mid = (l+r)>>1;if(c[mid] <= x){l = mid;}else {r = mid;}}if(c[r] > x) return n-r+1;return 0;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;ll cnt = 0;for(int i = 1;i <= n;i++)cin>>a[i];for(int i = 1;i <= n;i++)cin>>b[i];for(int i = 1;i <= n;i++)cin>>c[i];//因為要二分a[i]和c[i],所以我們需要對其進行排序操作sort(a+1,a+1+n);sort(c+1,c+1+n);for(int i = 1;i <= n;i++){ll x = bs1(b[i]);ll y = bs2(b[i]);cnt += x * y;//每個 a[j] 可以與每個 c[z] 組合}cout<<cnt<<"\n";return 0;
}
P2440 木材加工
P2440 木材加工
很明顯這道題就是二分答案，跟二分查找略顯不同的是,它需要一個證明的過程判斷結果的正確性
廢話少說,上代碼
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;
ll a[N];
ll n,k;
bool check(int mid,int k)//長度為mid，段數為k
{int cnt = 0;for(int i = 1;i <= n;i++){cnt += a[i] / mid;}if(cnt >= k)return true;else return false;
}
int main()
{cin>>n>>k;ll sum = 0;for(int i = 1;i <= n;i++)cin>>a[i];for(int i = 1;i <= n;i++){sum += a[i];}if(sum < k)cout<<0<<"\n";else //需要二分之前先對木材進行排序{sort(a+1,a+1+n);ll l = -1,r = 1e8+10;while(l+1 != r){ll mid = (l+r) >> 1;if(check(mid,k)){l = mid;}else r = mid;}cout<<l<<"\n";}return 0;
}
