NC20910. 营救
描述
输入描述
第一行一个数N(N≤106)，表示有N个点。
第二行有N个整数，第i个整数xi (xi≤107)个表示第i个点的坐标
之后的一行N个整数ai (ai≤100000)，表示每一个点的影响值。
输出描述
只有一行，包含一个整数，表示最多能够经过的点的数量。
示例1
输入:
5 1 5 7 8 12 2 1 5 2 3
输出:
3
C++11(clang++ 3.9) 解法, 执行用时: 801ms, 内存消耗: 12152K, 提交时间: 2020-04-05 21:59:25
#include<bits/stdc++.h>
using namespace std;
int i,j,s,N;
struct h{
int l,r;
} q[1000003];
bool cmp(h A,h B){
if(A.r==B.r) return A.l>B.l;
return A.r<B.r;
}
int a[1000003];
int main(){
cin>>N;
for(i=0;i<N;i++) cin>>a[i];
for(i=0;i<N;i++) cin>>j,q[i].l=max(0,a[i]-j),q[i].r=a[i]+j;
sort(q,q+N,cmp);
for(i=j=s=0;i<N;i++)
if(q[i].l>=j) j=q[i].r,s++;
cout<<s;
}