对于任意两个斑羚而言,如果它们都可以单独越过,可以确定这两个斑羚的最大贡献是二,如果一个可以单独越过,可以确定这两个斑羚的最大贡献是一,如果两个都不能单独越过,那么如果可以贡献1的价值,一定是一只通过另一只实现飞过,那么为了确保可以踩,一定是在一只斑羚跳到了最大值时踩,为了确保可以踩过,一定是y更大的踩在y小的斑羚身上过去。

故两只斑羚满足min(x1,x2)+max(y1,y2)≥m时可以贡献1的价值

可以证明如果两只斑羚都满足xi+yi≥m时一定可以贡献1的价值

下图为证明过程 alt 在证明时发现两只斑羚都满足xi+yi=m时,min(x1,x2)+max(y1,y2)=m。

故xi+yi<m时,min(x1,x2)+max(y1,y2)<m,两只斑羚不可能实现飞渡贡献为0。

那么当一只斑羚满足x1+y1≥m,另一种满足x2+y2<m时怎么样可以贡献1的价值呢?

显然,当x2大于等于x1时,可以贡献。

排序后贪心求解便可以得到最优解