做网站赚钱难,重庆 网站 备案 查询,wordpress 鼠标悬停,找人设计网页多少钱P1102 A-B 数对
P1102 A-B 数对 暴力枚举还是很好做的#xff0c;直接上双层循环OK 二分思路:查找边界情况#xff0c;找出最大下标和最小下标#xff0c;两者相减1即为答案所求 废话不多说#xff0c;上代码
//暴力O(n^3) 72pts
// #includebits/stdc.h
// usin…P1102 A-B 数对
P1102 A-B 数对 暴力枚举还是很好做的直接上双层循环OK 二分思路:查找边界情况找出最大下标和最小下标两者相减1即为答案所求 废话不多说上代码
//暴力O(n^3) 72pts
// #includebits/stdc.h
// using namespace std;
// const int N 1100;
// int a[N],b[N],c[N];// int main()
// {
// int n;cinn;
// int cnt 0;
// for(int i 1;i n;i)cina[i];
// for(int i 1;i n;i)cinb[i];
// for(int i 1;i n;i)cinc[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;
// }
// }
// }
// coutcnt\n;
// return 0;
// }#includebits/stdc.h
using namespace std;
const int N 1e510;
using ll long long;
ll a[N],b[N],c[N];
ll n;
int bs1(int x)
{ll l -1,r n1;while(l1 ! r){ll mid (lr)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 n1;while(l1 ! r){ll mid (lr)1;if(c[mid] x){l mid;}else {r mid;}}if(c[r] x) return n-r1;return 0;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinn;ll cnt 0;for(int i 1;i n;i)cina[i];for(int i 1;i n;i)cinb[i];for(int i 1;i n;i)cinc[i];//因为要二分a[i]和c[i],所以我们需要对其进行排序操作sort(a1,a1n);sort(c1,c1n);for(int i 1;i n;i){ll x bs1(b[i]);ll y bs2(b[i]);cnt x * y;}coutcnt\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 和 n1,因为你的c[i]最终要返回 n-r1,所以你需要把指针定在n1上,确保搜索范围的右边界在数组外。这样可以避免数组越界的问题 废话不多说上代码
//暴力O(n^3) 72pts
// #includebits/stdc.h
// using namespace std;
// const int N 1100;
// int a[N],b[N],c[N];// int main()
// {
// int n;cinn;
// int cnt 0;
// for(int i 1;i n;i)cina[i];
// for(int i 1;i n;i)cinb[i];
// for(int i 1;i n;i)cinc[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;
// }
// }
// }
// coutcnt\n;
// return 0;
// }#includebits/stdc.h
using namespace std;
const int N 1e510;
using ll long long;
ll a[N],b[N],c[N];
ll n;
int bs1(int x)
{ll l -1,r n1;while(l1 ! r){ll mid (lr)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 n1;while(l1 ! r){ll mid (lr)1;if(c[mid] x){l mid;}else {r mid;}}if(c[r] x) return n-r1;return 0;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinn;ll cnt 0;for(int i 1;i n;i)cina[i];for(int i 1;i n;i)cinb[i];for(int i 1;i n;i)cinc[i];//因为要二分a[i]和c[i],所以我们需要对其进行排序操作sort(a1,a1n);sort(c1,c1n);for(int i 1;i n;i){ll x bs1(b[i]);ll y bs2(b[i]);cnt x * y;//每个 a[j] 可以与每个 c[z] 组合}coutcnt\n;return 0;
}P2440 木材加工
P2440 木材加工 很明显这道题就是二分答案跟二分查找略显不同的是,它需要一个证明的过程判断结果的正确性 废话少说,上代码
#includebits/stdc.h
using namespace std;
using ll long long;
const int N 1e510;
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()
{cinnk;ll sum 0;for(int i 1;i n;i)cina[i];for(int i 1;i n;i){sum a[i];}if(sum k)cout0\n;else //需要二分之前先对木材进行排序{sort(a1,a1n);ll l -1,r 1e810;while(l1 ! r){ll mid (lr) 1;if(check(mid,k)){l mid;}else r mid;}coutl\n;}return 0;
}
