xtu oj Distance
回顾
- A+B III
- 问题 H: 三角数
- 问题 G: 3个数
- 等式 数组下标查询，降低时间复杂度
- 1405 问题 E: 世界杯
- xtu 数码串
- xtu oj 神经网络
- xtu oj 1167 逆序数（大数据）
- xtu oj 原根
- xtu oj 不定方程的正整数解
- xtu oj 最多的可变换字符串
- xtu oj String I
- xtu oj 字母序列
- xtu oj 分段
- xtu oj 完全平方数II
- xtu oj 连接字符串
- xtu oj 2021
- xtu oj 数字
- xtu oj 删除
- xtu oj 聚会
代码
#include<stdio.h>
#define N 100010
int a[N],b[N];
void sort(int q[],int l,int r){//快速排序模板
if(l>=r){
return;
}
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
sort(q,l,j);
sort(q,j+1,r);
}
int myabs(int x){//绝对值函数
if(x<0){
return -x;
}
return x;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
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,0,n-1);//排序
sort(b,0,m-1);
int ans=1e9+10;
int i=0,j=0;//双指针
while(i<n&&j<m){
if(myabs(a[i]-b[j])<ans){//更新答案
ans=myabs(a[i]-b[j]);
}
if(a[i]<b[j]){//这里是关键哈哈，就是我们想要两个数字的差距尽可能小，那就需要 a 里面小的元素尽可能接近 b 里面大的元素
i++;//最小的答案是 0 ,假设 a 里面的元素更大，那需要一个更大的 b 来试图找到一个更优的答案，这样两个元素才可能更加
}else{//接近
j++;
}
}
printf("%d\n",ans);
}
return 0;
}
思路
再写一题就去复习服务端。
这个题有点像曼哈顿距离，曼哈顿距离是 |x1-x2|+|y1-y2| ，这个是 |x-y|
求这个最小的距离，我感觉就是用最小的元素去比较一下就好了，最小的元素和最大的元素，首先排序一下，然后计算最大的元素和最大的元素，最小的元素和最小的元素，最大的元素和最小的元素，也就是说有效的元素最多就是四个元素，a,b 两个数组的最大值和最小值，感觉是这样子，写一下试试。
#include<stdio.h>
#define N 100010
int a[N],b[N];
void sort(int q[],int l,int r){//快速排序模板
if(l>=r){
return;
}
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
sort(q,l,j);
sort(q,j+1,r);
}
int myabs(int x){//绝对值函数
if(x<0){
return -x;
}
return x;
}
int mymin(int x,int y){//求最小值
if(x<y){
return x;
}
return y;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
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,0,n-1);//排序
sort(b,0,m-1);
int ans1=myabs(a[0]-b[0]),ans2=myabs(a[0]-b[m-1]),ans3=myabs(a[n-1]-b[0]),ans4=myabs(a[n-1]-b[m-1]);
int temp1=mymin(ans1,ans2);//求最小值
int temp2=mymin(ans3,ans4);
int ans=mymin(temp1,temp2);
printf("%d\n",ans);
}
return 0;
}
为啥直接 WA 了呢。
嗷嗷，我知道了，就是答案不一定是在端点的地方，数组中间可能有元素更加接近。用双指针找一下最优的答案就好。可能最难想到的就是啥时候更新指针，两个元素越接近，答案就越优，所以假设 a 里面的元素小于 b 里面的元素，就用更大的 a 的元素，这样就能得到更优的答案。
最近从朋友那里学了 qsort 那里的 cmp 指针啥的是啥意思，现在把快排的模板换掉，试着写一下，考试的时候确实用封装好的函数会爽一些。
#include<stdio.h>
#include<stdlib.h>
#define N 100010
int a[N],b[N];
int cmp(const void *a,const void *b){
return (*(int*)a-*(int*)b);
}
int myabs(int x){//绝对值函数
if(x<0){
return -x;
}
return x;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
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]);
}
qsort(a,n,sizeof(a[0]),cmp);//排序
qsort(b,m,sizeof(b[0]),cmp);
int ans=1e9+10;
int i=0,j=0;//双指针
while(i<n&&j<m){
if(myabs(a[i]-b[j])<ans){//更新答案
ans=myabs(a[i]-b[j]);
}
if(a[i]<b[j]){//这里是关键哈哈，就是我们想要两个数字的差距尽可能小，那就需要 a 里面小的元素尽可能接近 b 里面大的元素
i++;//最小的答案是 0 ,假设 a 里面的元素更大，那需要一个更大的 b 来试图找到一个更优的答案，这样两个元素才可能更加
}else{//接近
j++;
}
}
printf("%d\n",ans);
}
return 0;
}
qsort 在 stdlib.h 这个头文件里面，四个参数按照上面代码里面写就好了，第一个参数是数组，第二个参数是数组长度，第三个参数是一个元素的大小，第四个参数是比较函数，比较函数需要按照上面的格式写，因为底层函数定义的时候是这样定义的。
比较函数的返回值的时候，第一个 * 表示的意思是解引用，解引用就是取某地址的元素的值，第二个 * 表示的是强制转换指针类型，把空指针转换成 int 类型的指针。
感觉考试一定会考排序，所以读者一定要学会快速排序模板或者 qsort 函数的使用，因为冒泡排序的时间复杂度是平方的，可能在用的时候超时，快速排序的时间复杂度是 O(nlogn) ，一般是可以接受的。
原文地址：https://blog.csdn.net/L3102250566/article/details/143746920
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！