矿石样本分析【算法赛】（蓝桥杯）

题目来源：6.矿石样本分析【算法赛】 - 蓝桥云课 (lanqiao.cn)

写在前面：写这题时没有思路，开2重循环会超时就放弃了这题，导致这次小白赛没AK，所以赛后重新补了这道题（看完思路是真简单啊）······。

回归正题：

题意：给定n个数，找出这n个数中其中两个数相加的值为k，找出其中经过时间最少的两个数（可以从左右分头找），若找不到直接输出-1。

思路：贪心+枚举，将这n个数的下标存入map里面，然后判断枚举两个机器的出发点即可。

实现代码：

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int> 
using namespace std;
const int N=2e5+5;
int a[N];
map<int,vector<int>> m;//必须用map存储，1e9超出数组范围
void solve(){
	int n,k;
	cin >> n >> k;
    int ans=INT_MAX;//定义为最大正整数
	for(int i=1;i<=n;++i) cin >>a[i];
	for(int i=1;i<=n;++i){
		m[a[i]].push_back(i);//标记下标
	}
	for(int i=1;i<=n;++i){
		if(m[k-a[i]].size()==0||k-a[i]==a[i]) continue;//若找不到或者这两个数相等，跳过
		else{
			for(auto t : m[k-a[i]]){//遍历数组
				ans=min(ans,max(min(i,n-i+1),min(t,n-t+1)));//ans找的最小值，这两个数所经过路径的时间也是找最小值，但两者所经过的时间找的是这两个路径最大的数
			}
		}
	}
	if(ans==INT_MAX) cout << -1 << endl;//找不到输出-1
	else cout << ans << endl;
	return ;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}