题解：P10444 「MYOI-R3」极差

wrh316 · 2024-05-12 21:23:40 · 题解

先对数组 a 从小到大排序，排序后 a _ {1} 一定是极小值，而 a _ {n} 一定是最大值。

如果能找到两个数 a _ {x} 和 a _ {y} 使得 a _ {x} 减去 a _ {1} 和 a _ {n} 减去 a _ {y} 相等并且 y 比 x 要小的话，就一定可以将整个序列分成两半。

我们可以想到：a _ {x} 减去 a _ {1} 和 a _ {n} 减去 a _ {y} 相等就是 a _ {x} 加上 a _ {y} 和 a _ {1} 加上 a _ {n} 相等，所以枚举 y，二分查找是否能找到对应的 x，就完成了。

上代码：

#include <bits/stdc++.h>
using namespace std;

int t,id,n,ans;
int a[1000005];
bool f;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t>>id;
    while(t--){
        cin>>n;
        for(int i = 1;i <= n;i++) cin>>a[i];
        sort(a + 1,a + n + 1);
        ans = a[1] + a[n];
        f = false;
        for(int i = 2;i <= n - 1;i++){
            bool vis = binary_search(a + i + 1,a + n,ans - a[i]);
            if(vis){
                cout<<"Yes\n";
                f = true;
                break;
            }
        }
        if(!f) cout<<"No\n";
    }
    return 0;
}