题意
\(a\) 和 \(b\) 两个长度为 \(n\) 的序列中，\(i\) 和 \(j\) 为序列的下标同时满足 \(i<j<n\)，求在满足 \((a_j-b_i) \times (b_j+b_i) = a_j \times b_i +a_i \times b_j\) 中最小的 \(j\)，若不存在则输出 \(-1\)。
思路
因式分解
\[(a_j-b_i) \times (b_j+b_i) = a_j \times b_i +a_i \times b_j
\]
\[a_j \times b_j + a_j \times b_i - b_i \times b_j-b_i^2 = a_j \times b_i +a_i \times b_j
\]
移项与合并可得
\[a_j \times b_j+a_i \times b_j-a_i\times b_j=b_i^2
\]
\[b_j\times(a_j+a_i+b_i)=b_i^2
\]
因为此题数据范围较小，可以枚举 \(b_j\) 的值，所以只需求出 \(a_i\) 的值来解此题。
可使用 map 来求解。
解析
创建一个 map 维护 \(i\) 与其对应的 \(j\)，用数组记录所有 \(j\) 的值，并找出最小的 \(j\)。
找出最小值可以先定义一个极大值，再使用 \(\min\) 函数求出所求的最小 \(j\)。若仍为极大值则输出 \(-1\) 即无解。
代码
#include<bits/stdc++.h>
using namespace std;
stack<int> abc;
int n,a[100001],b[100001],c,ans[100001]={0};
map<pair<int,int>,int> maap;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=n;i>=1;--i)
{
c=0x7fffffff;
for (int j=1;j<=b[i];++j)
if(b[i]*b[i]%j==0)
{
int x=0,y=0;
if(maap[pair<int,int>(a[i]+b[i]+j,b[i]*b[i]/j)])
x=maap[pair<int,int>(a[i]+b[i]+j,b[i]*b[i]/j)];
if(maap[make_pair(a[i]+b[i]+b[i]*b[i]/j,j)])
y=maap[pair<int,int>(a[i]+b[i]+b[i]*b[i]/j,j)];
if(x!=0)
c=min(c,x);
if(y!=0)
c=min(c,y);
}
if(c!=0x7fffffff)
abc.push(c);
else
abc.push(-1);
maap[make_pair(a[i],b[i])]=i;
}
for(int i=1;i<=n;i++)
{
cout<<abc.top()<<endl;
abc.pop();
}
}