题解：P6393 隔离的日子

di1236 · 2025-12-13 21:28:45 · 题解

P6393 隔离的日子

题意

给定 n 个栗子，每个栗子有甜度 a_i 和咸度 b_i。对于每个栗子 i，需要找到最小的 j（i < j \le n），使得 (a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j。

思路

我们发现，上面这个式子可以化简为 b_j \times (a_j - a_i - b_i) = b_i^2。然后发现 1 \leq n \leq 5 \times 10^4 那么我们就可以双重循环枚举每个栗子是否为最佳搭配就好了。当然，我们需要一些优化。

AC 代码

请勿抄袭

#include<bits/stdc++.h>
#define by using
#define di namespace 
#define awa std 
by di awa;
struct di1236{
    long long a;  // 甜度 a
    long long b;  // 咸度 b
}d[50002];
int n;
bool flag;
inline long long read(){//快读，用来优化代码 
    long long k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = k * 10 + (c - '0');
        c = getchar();
    }
    return  k * f;
}
int main() {
    n = read();
    for (int i=1;i<=n;++i){
       d[i].a=read();
       d[i].b=read();
    }
    for (int i=1;i<n;++i){//循环又1到n-1是因为最后一个栗子永远无法匹配 
        bool flag=0;
        long long d1=d[i].a,d2=d[i].b,d3= b_i*b_i;//记录当前这个栗子的甜度咸度，bb为当前栗子的咸度平方(化简后的式子会用到) 
        for (int j=i+1;j<=n;++j) {
            long long d4=d[j].a,d5=d[j].b;//我们枚举到的当前栗子的甜咸度 
            if (d5*(d4-d1-d2)==d3){//上面提到的化简后的式子 
                printf("%d\n",j);
                flag=1;
                break;
            }
        }
        if (!flag){//若刚才没找到，就输出-1； 
            printf("-1\n");
        }
    }
    printf("-1\n");//最后一个栗子无法匹配 
    return 0;
}