牛客网题集——Min Value（逻辑）

Min Value

牛客网测试平台
题意：一个由 N 个数组成的序列 a₁，a₂，a₃，······，a_n-1，a_n，从中任选两个数 a_i 和 a_j，使得 a_i + a_j 的绝对值最小，并且计算出 i + j 的值，其中 i ≠ j。

输入描述:
输入第一行包含一个正整数 N (2 ≤ N ≤ 100000)
接下来 N 行，每行一个整数 ai (1 ≤ i ≤ N，-10⁶ ≤ a_i ≤ 10⁶)
输出描述:
输出两个数，中间用空格分开，a_i + a_j 的绝对值的最小值和 i + j
（如果有多组 i 和 j 满足条件，输出 i + j 最小的一组）

示例1
输入
5
-2
6
7
7
-8
输出
1 8
说明
满足最小值的有两种情况，选(3，5)或(4，5)，(3 + 5) < (4 + 5)，因此输出 1 和 8

该题逻辑想清楚后并不是很复杂，但是有一些特殊情况需要特别注意。
解题步骤：
①、存储数据：利用 node 结构体存储数据

struct node{
	int n;	//存储值
	int xb;	//存储下标
}arr[100010];

②、排序：对于 arr 结构体数组中每个两个结构体元素 n 从大到小排序，当两个结构体元素 n 相等时，按下标从小到大排序。

bool cmp(node a, node b){
	if(a.n==b.n){
		return a.xb<b.xb;
	}
	return a.n<b.n;
}
sort(arr, arr+n, cmp);

③、维护最小绝对值及最小下标差：创建check( i, j )函数，用于检查下标为 i 与 j 的元素是否为为最小绝对值及下标差。

void check(int a, int b){
	if(tmp>abs(arr[a].n+arr[b].n)){
		tmp = abs(arr[a].n+arr[b].n);
		ans_xb=arr[a].xb+arr[b].xb;
	}
	if(tmp==abs(arr[a].n+arr[b].n))
		ans_xb=min(ans_xb, arr[a].xb+arr[b].xb);
}

④、在可能出现最小绝对值及最小下标差的地方进行check。

在代码中，我采用了双指针的方式扫描结构体数组。
时间复杂度O(n)

#include<cstdio>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int tmp=1000010, ans_xb=200010;
struct node{
	int n;
	int xb;
}arr[100010];

//维护最小tmp、ans_xb 
void check(int a, int b){
	if(tmp>abs(arr[a].n+arr[b].n)){
		tmp = abs(arr[a].n+arr[b].n);
		ans_xb=arr[a].xb+arr[b].xb;
	}
	if(tmp==abs(arr[a].n+arr[b].n))
		ans_xb=min(ans_xb, arr[a].xb+arr[b].xb);
}

bool cmp(node a, node b){
	if(a.n==b.n){
		return a.xb<b.xb;
	}
	return a.n<b.n;
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i].n);
		arr[i].xb=i+1;
	}
	sort(arr, arr+n, cmp);
	
	int l=0, r=n-1;
	while(l<r){
		//若剩下的数据相同，直接退出循环 
		if(arr[l].n==arr[r].n){
			check(l, l+1);
			break;
		}
		
		//读取相同的元素 
		while(arr[r].n==arr[r-1].n) r--;
		check(r, r-1); 	//可能出现较小的下标、绝对值
		check(l, r);
		check(l, l+1);
		while(arr[l].n==arr[l+1].n) l++;
		
		if(arr[l].n+arr[r].n<0) l++;
		else r--;
	}
	printf("%d %d", tmp, ans_xb);
	
	return 0;
}

如果觉得对你有帮助，其实可以关注我的 : )