文章目录
两个有序数组的归并 51Nod - 2062
题目描述
输入一个整数n（n <= 10000）和n个整数a[i]，保证这n个整数已按照从小到大进行排序。然后输入一个整数m（m <= 10000），和m个整数b[j]，保证这m个整数已按照从小到大进行排序。
将两组数归并后输出。
输入格式
第一行输入一个整数n。 接下来n行，每行输入一个整数a[i]。 接下来1行输入一个整数m。 接下来m行，每行输入一个整数b[j]。
输出格式
n+m行，一行一个整数。
输入样例
3
1
3
6
3
0
4
5
输出样例
0
1
3
4
5
6
- 参考程序
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N], temp[N];
void mergeSort(int a[],int l,int r){
if(l>=r) return;
int mid=(l+r)/2;
mergeSort(a, l, mid); //分治，其实这里可以省略
mergeSort(a, mid+1, r);
// 归并
int i=l, j=mid+1, p=0;
while(i<=mid && j<=r){
if(a[i] < a[j]) temp[++p] = a[i++];
else temp[++p] = a[j++];
}
while(i<=mid) temp[++p]=a[i++];
while(j<=r) temp[++p]=a[j++];
for(int i=1; i<=p; i++) a[l++]=temp[i];
}
int main(){
// freopen("data.in", "r", stdin);
int n,m;
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i=n+1; i<=n+m; i++) scanf("%d", &a[i]);
mergeSort(a,1,n+m);
for(int i=1; i<=n+m; i++){
printf("%d\n", a[i]);
}
return 0;
}
二分查找（一） 计蒜客 - T1560
题目描述
蒜头君手上有个长度为 n 的数组 A。
由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问整数 x 是否在数组AA 中。
输入格式
第一行输入两个整数 n 和 m，分别表示数组的长度和查询的次数。
接下来一行有 nn 个整数 ai。
接下来 m 行，每行有 1 个整数 x，表示蒜头君询问的整数。
输出格式
对于每次查询，如果可以找到，输出"YES"，否则输出"NO"。
输入样例
10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10
输出样例
NO
YES
NO
YES
NO
- 参考程序
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
bool binSearch(int*arr,int x){
int l=0,r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(arr[mid]>x) r=mid-1;
else if(arr[mid]<x) l=mid+1;
else if(arr[mid]==x) return 1;
}
return 0;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
for(int i=0; i<m; i++) scanf("%d", &b[i]);
sort(a, a+n);
for(int i=0; i<m; i++){
printf("%s\n", binSearch(a,b[i]) ?"YES":"NO");
}
return 0;
}
二分查找（二） 计蒜客 - T1561
题目描述
蒜头君手上有个长度为 n 的数组 A。
由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 A 中，大于等于 x 的最小值是多大？
输入格式
第一行输入两个整数 n 和 m，分别表示数组的长度和查询的次数。
接下来一行有 n 个整数 ai。
接下来 m 行，每行有 1 个整数 x，表示蒜头君询问的整数。
输出格式
对于每次查询，如果可以找到，输出这个整数。
否则输出 -1。
数据范围：1≤n,m≤1e5,0≤x≤1e6。
输入样例
10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10
输出样例
1
1
5
9
-1
- 参考程序
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
//二分查找第一个不小于的元素
int lower_bound(int*arr,int x){
int l=0,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(arr[mid]>=x) r=mid;
else if(arr[mid]<x) l=mid+1;
}
if(a[l]>=x) return a[l];
return -1;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
for(int i=0; i<m; i++) scanf("%d", &b[i]);
sort(a, a+n);
for(int i=0; i<m; i++){
printf("%d\n", lower_bound(a,b[i]));
}
return 0;
}
二分查找（三） 计蒜客 - T1562
题目描述
蒜头君手上有个长度为 n 的数组 A。
由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 A 中，比 x 大的最小值是多大？
但是这次蒜头君要求这个数字必须大于 x，不能等于 x。
输入格式
第一行输入两个整数 n 和 m，分别表示数组的长度和查询的次数。
接下来一行有 n 个整数 ai。
接下来 m 行，每行有 1 个整数 x，表示蒜头君询问的整数。
输出格式
对于每次查询，如果可以找到，输出这个整数。
否则输出 -1。
数据范围：1≤n,m≤1e5,0≤x≤1e6。
输入样例
10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10
输出样例
1
2
5
-1
-1
- 参考程序
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
//二分查找第一个大于的元素
int upper_bound(int*arr,int x){
int l=0,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(arr[mid]>x) r=mid;
else if(arr[mid]<=x) l=mid+1;
}
if(a[l]>x) return a[l];
return -1;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
for(int i=0; i<m; i++) scanf("%d", &b[i]);
sort(a, a+n);
for(int i=0; i<m; i++){
printf("%d\n", upper_bound(a,b[i]));
}
return 0;
}
二分查找（四） 计蒜客 - T1563
题目描述
蒜头君手上有个长度为 n 的数组 A。
由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 A 中，等于 xx 的数字有多少个？
输入格式
第一行输入两个整数 n 和 m，分别表示数组的长度和查询的次数。
接下来一行有 n 个整数 ai。
接下来 m 行，每行有 1 个整数 x，表示蒜头君询问的整数。
输出格式
对于每次查询，输出一个整数，表示数组 A 中有多少个 x。
数据范围：1≤n,m≤1e5,0≤x≤1e6。
输入样例
10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10
输出样例
0
3
0
1
0
- 参考程序
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
//等于 xx 的数字有多少个
int binSearch(int*arr,int x){
int l=0,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(arr[mid]>=x) r=mid;
else if(arr[mid]<x) l=mid+1;
}
for(r=l; arr[r]==x; r++);
return r-l;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
for(int i=0; i<m; i++) scanf("%d", &b[i]);
sort(a, a+n);
for(int i=0; i<m; i++){
printf("%d\n", binSearch(a,b[i]));
}
return 0;
}
查找 洛谷 - P2249
题目描述
输入 n(n≤1e6) 个不超过 1e9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a[1…n]，
然后进行 m(m≤1e5) 次询问。
对于每次询问，给出一个整数 q(q≤1e9)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
m 个整数表示答案。
输入样例
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出样例
1 2 -1
说明/提示：1e6 规模的数据读入，请用 scanf。用 cin 会超时。
- 参考程序
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N], b[N];
int binSearch(int* arr, int x){
int l=1, r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(arr[mid]<x) l=mid+1;
else if(arr[mid]>x) r=mid-1;
else if(arr[mid]==x){
if(mid>1 && arr[mid-1]==x) r=mid-1;
else return mid;
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=m; i++) cin>>b[i];
for(int i=1; i<=m; i++) printf("%d ", binSearch(a, b[i]));
return 0;
}
求第 k 小的数 洛谷 - P1923
题目描述
输入 n（1≤n<5000000 且 n为奇数）个数字 ai （1≤ai<1e9），输出这些数字的第 k 小的数。最小的数是第 0 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入样例
5 1
4 3 2 1 5
输出样例
2
- 参考程序
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int a[N], n, k;
void quickSort(int*arr, int l, int r){
if(l>=r) return;
int i=l, j=r, mid=arr[l];
while(i<j){
while(i<j && arr[j]>mid) j--; a[i]=a[j];
while(i<j && arr[i]<=mid) i++; a[j]=a[i];
}
a[i]=mid;
if(k<=i-1) quickSort(arr, l, i-1);
if(k>=i+1) quickSort(arr, i+1, r);
}
int main(){
// freopen("data.in", "r", stdin);
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
// nth_element(a, a+k, a+n);
quickSort(a, 0, n-1);
printf("%d\n", a[k]);
return 0;
}
A-B 数对 洛谷 - P1102
题目描述
给出一串数以及一个数字 C，要求计算出所有 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个整数 N, C。
第二行，N 个整数，作为要求处理的那串数。
输出格式
一行，表示该串数中包含的满足 A - B = C 的数对的个数。
输入样例
4 1
1 1 2 3
输出样例
3
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×1e5。
保证所有输入数据绝对值小于2^30，且 C≥1。
- 参考程序
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],n,c;
long long ans=0;
int binSearch_left(int *arr, int l, int r, int x){
while(l<=r){
int mid=(l+r)/2;
if(arr[mid]==x) r=mid-1;
else if(arr[mid]>x) r=mid-1;
else if(arr[mid]<x) l=mid+1;
}
if(arr[l]==x) return l;
return -1;
}
int binSearch_right(int *arr, int l, int r, int x){
while(l<=r){
int mid=(l+r)/2;
if(arr[mid]==x) l=mid+1;
else if(arr[mid]>x) r=mid-1;
else if(arr[mid]<x) l=mid+1;
}
if(arr[r]==x) return r;
return -1;
}
int main(){
// freopen("data.in", "r", stdin);
cin>>n>>c;
for(int i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
for(int i=n-1; i>=0; i--){
int x = a[i]-c;
int l=binSearch_left(a,0,n-1, x);
int r=binSearch_right(a,0,n-1, x);
if(l!=-1 &&r!=-1) ans += (r-l+1);
}
cout<<ans<<endl;
return 0;
}
EKO / 砍树 洛谷 - P1873
题目描述
伐木工人 Mirko 需要砍 M 米长的木材。
对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。
不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：
Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，
并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。
Mirko 就得到树木被锯下的部分。
例如，如果一排树的高度分别为 20,15,10 和 17，
Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，
而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。
请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。
换句话说，如果再升高 1 米，他将得不到 M 米木材。
输入格式
第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。
第 2 行 N 个整数表示每棵树的高度。
输出格式
1 个整数，表示锯片的最高高度。
输入样例
4 7
20 15 10 17
输出样例：15
输入样例
5 20
4 42 40 26 46
输出样例：36
说明/提示
对于 100% 的测试数据， 1≤N≤10e6，1≤M≤2×1e9，树的高度 <1e9，所有树的高度总和>M。
- 参考程序
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10, INF=2E9+1;
int n,m,a[N];
int check(int h){
int temp=0;
for(int i=n-1; a[i]>h; i--){
temp+=a[i]-h;
if(temp>INF) return INF;
}
return temp;
}
//查找不小于x的最后一个元素
int lower_bound(int l, int r, int x){
while(l<r){
int mid=(l+r)/2.0+0.5;
if(check(mid)>=x) l=mid;
else r=mid-1;
}
if(check(l)<x) return -1;
return l;
}
int main(){
// freopen("data.in", "r", stdin);
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
sort(a, a+n);
int l=a[0], r=a[n-1];
int ans=lower_bound(l, r, m);
printf("%d\n", ans);
return 0;
}
进击的奶牛 洛谷 - P1824
题目描述
Farmer John 建造了一个有 N(2≤N≤100000) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x[1…N] (0≤xi≤1000000000)。
他的 C(2≤C≤N) 头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。
为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。
那么，这个最大的最近距离是多少呢？
输入格式
第 1 行：两个用空格隔开的数字 N 和 C。
第 2 ~N+1 行：每行一个整数，表示每个隔间的坐标。
输出格式
输出只有一行，即相邻两头牛最大的最近距离。
输入样例
5 3
1
2
8
4
9
输出样例：3
- 参考程序
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N], n, c;
bool check(int x){ // 检查距离x是否合法
int l=a[1], num=1;// num 牛棚数量
for(int i=2; i<=n; i++){
if(l+x < a[i]) l=a[i], num++;
}
return num>=c;
}
int binSearch(int l,int r){
while(l<r){ // 所有牛中相邻两头的最近距离越大越好
int mid = (l+r)/2;
if(check(mid)) l=mid+1;
else r=mid;
}
return l;
}
int main(){
cin>>n>>c;
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1, a+1+n);
cout<<binSearch(0, a[n]-a[1])<<endl;
return 0;
}
一元三次方程求解 洛谷 - P1024
题目描述
有形如：ax^3 + bx^2 + cx + d = 0 这样的一个一元三次方程。
给出该方程中各项的系数（a,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 -100 至 100 之间），且根与根之差的绝对值 ≥1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。
提示：记方程 f(x) = 0，若存在 2 个数 x1 和 x2，且 x1 < x2，f(x1)×f(x2)<0，则在 (x1, x2) 之间一定有一个根。
输入格式
一行，4 个实数 a, b, c, d。
输出格式
一行，3个实根，从小到大输出，并精确到小数点后 2 位。
输入样例
1 -5 -4 20
输出样例
-2.00 2.00 5.00
- 参考程序
#include<bits/stdc++.h>
using namespace std;
double x1,x2,x3;
double a,b,c,d;
const double eps=1e-3;
double f(double x) {
return a*x*x*x+b*x*x+c*x+d;
}
double binarySearch(double l, double r) {
while(l<r && f(l)*f(r)<0) {
double mid=(l+r)/2;
if(fabs(f(mid))<=eps) return mid;
else if(f(l)*f(mid)<0) r=mid;
else if(f(mid)*f(r)<0) l=mid;
}
}
void fun1() {
// f(x) =ax^3+bx^2+cx+d
// f'(x)=3ax^2+2bx+c
double t1=((-2*b)-sqrt((2*b)*(2*b)-4*3*a*c))/(2*3*a);
double t2=((-2*b)+sqrt((2*b)*(2*b)-4*3*a*c))/(2*3*a);//极值
// -100 <= x1 < t1 < x2 < t2 < x3 <= 100
x1 = binarySearch(-100, t1);//[-100,t1)
x2 = binarySearch(t1, t2); //(t1,t2)
x3 = binarySearch(t2, 100); //(t2,100]
cout<<fixed<<setprecision(2)<<x1<<" "<<x2<<" "<<x3<<endl;
}
void fun2() { //暴力可过：200 * 100=2e4
for(double x=-100; x<=100; x+=0.01) {
if(fabs(a*x*x*x+b*x*x+c*x+d)<=eps) {
cout<<fixed<<setprecision(2)<<x<<" ";
}
}
}
int main() {
cin>>a>>b>>c>>d;
fun1();
// fun2();
return 0;
}
烦恼的高考志愿 洛谷 - P1678
题目描述
现有 m(m≤100000) 所学校，每所学校预计分数线是 ai(ai ≤1e6)。
有 n(n≤100000) 位学生，估分分别为 bi(bi≤1e6)。
根据n位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。
输入格式
第一行读入两个整数m，n，m表示学校数，n表示学生数。
第二行共有m个数，表示m个学校的预计录取分数。
第三行有n个数，表示n个学生的估分成绩。
输出格式：一行，为最小的不满度之和。
输入样例
4 3
513 598 567 689
500 600 550
输出样例：32
数据范围：
对于30%的数据，m，n<=1000,估分和录取线<=10000;
对于100%的数据，n,m<=100,000,录取线<=1000000。
- 参考程序
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N], b[N];
int find(int arr[], int n, int m){
int l=1,r=n, mid;
while(l<r){//二分查找恰好第一个不小于的 a[r]
mid=(l+r)/2;
if(arr[mid]<m) l=mid+1;
else if(arr[mid]>=m) r=mid;
}
// printf("l=%d r=%d mid=%d a[r-1]=%d m=%d a[r]=%d\n",l,r,mid,a[r-1], m,a[r]);
if(r>1 && abs(arr[r-1]-m) < abs(arr[r]-m)) r=r-1;
return r;
}
int main(){
int m,n; cin>>m>>n;
for(int i=1; i<=m; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
sort(a+1, a+1+m);
int ans=0;
for(int i=1; i<=n; i++){
int id = find(a, m, b[i]);
ans += abs(a[id]-b[i]);
}
printf("%d\n", ans);
return 0;
}
三分法 洛谷 - P3382
题目描述
给出一个 N 次函数，保证在范围 [l, r]内存在一点 x，使得 [l, x]上单调增，[x, r]上单调减。试求出 x 的值。
输入格式
第一行一次包含一个正整数 N 和两个实数 l, r，含义如题目描述所示。
第二行包含 N + 1 个实数，从高到低依次表示该 N 次函数各项的系数。
输出格式
输出为一行，包含一个实数，即为 x 的值。
若你的答案与标准答案的相对或绝对误差不超过 10^(-5) 则算正确。
输入样例
3 -0.9981 0.5
1 -3 -3 1
输出样例：-0.41421
说明/提示
对于 100% 的数据，6≤N≤13，函数系数均在 [-100,100] 内且至多 15 位小数，|l|,|r| ≤10 且至多 15 位小数。l≤r。
- 参考程序
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const double eps = 1e-5;
const int N=20;
int n;
double l,r,a[N];
double f(double x){
double ans=0;
for(int i=n; i>=0; i--) ans=ans*x+a[i];
return ans;
}
int main(){
cin>>n>>l>>r;
for(int i=n; i>=0; i--) cin>>a[i];
while(r-l>=eps){
double m1=l+(r-l)/3.0;
double m2=r-(r-l)/3.0;
if(f(m1) < f(m2)) l = m1;
else r = m2;
}
cout<<fixed<<setprecision(5)<<l<<endl;
return 0;
}
