原题链接：Birthday Gift

题意简述

给定两个数组 例如 a=[1 3 5 4 2] b=[2 4 3 5 3] 从 A,B中选出两个索引 如选x,y(1<=x,y<=5（五个数）) 那么他的得分就是min(a[x]+b[y],b[y]+a[x]) 我们的目的就是选出两个索引是的其得分最大 观察他的数据范围是2e5 因此我们要考虑时间复杂度O(N^2)以下

思路分析

这题用二分做，效率为O(nlogn) 但比赛时没有想到，看到有大佬提出可以借鉴深度学习中NMS算法

具体思路： 假如一个索引，他比另一个数，上下都大，那么另一个数就没有存在的意义了，但是注意并不是所有的都比他小的数都删去，第二小以后的才删去

结构体：

struct f { int a, b; bool operator < (const f & p) const { return a < p.a; } } x[maxn];

删除过程：

for(int i=n;i>=1;i--) { int flag=0; if(x[i].b==-1) continue; for(int j=i-1;j>=1;j--) { if(x[j].b==-1) continue; if(x[i].b>=x[j].b) { if(flag) x[j].b=-1; else flag=1; } } }

但这种做法有缺陷，极端样例过不了 (1,n);(2,n-1);(3,n-2)…(n,1)就爆了

虽然这种方法AC了，可能是样例太弱了 记录一下这种思想

源代码：

#include <bits/stdc++> using namespace std; const int maxn = 2e6 + 10; int n; struct f { int a, b; bool operator < (const f & p) const { return a < p.a; } } x[maxn]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &x[i].a); for (int i = 1; i <= n; ++i) scanf("%d", &x[i].b); sort(x+1, x+n+1); for(int i=n;i>=1;i--) { int flag=0; if(x[i].b==-1) continue; for(int j=i-1;j>=1;j--) { if(x[j].b==-1) continue; if(x[i].b>=x[j].b) { if(flag) x[j].b=-1; else flag=1; } } } int ans = -1; for(int i=1; i<= n; i++) { if (x[i].b == -1) continue; for(int j=i+1; j<= n;j++) { if (x[j].b == -1) continue; ans=max(ans,min(x[i].a+x[j].b,x[j].a+x[i].b)); } } printf("%d\n", ans); return 0; }