首页 > 代码库 > hdu 5720
hdu 5720
考虑三个树枝:a,b,c
若c是将要抛出的树枝,那么形成三角形的条件是
a+b>c and a-b<c 可以写成 c属于开区间(a-b,a+b)
对于每个C和许许多多的其他边，如何保证C不构成三角形?
可以看到：对于每个a,要使得这个(a-b,a+b)尽可能的大,就要让b在小于a的基础上尽可能地大
那么我们可以排序等到n-1个这样的区间。只要C不在这些区间内,就一定不会构成三角形。
那么问题转化为区间问题了。
我们把包含在(L,R)区间且不与以上的所有区间相交的部分累加起来就得到了结果
首先离散化,-1代表进区间,1代表出区间
1.当上一个区间已经出来而进入下一个区间时,两个区间中间的部分可以积累
2.L到第一个区间的左边界可以积累
3.最后一个区间的有边界到R可以积累
#include <bits/stdc++.h>#define MP(x,y) make_pair(x,y)using namespace std;typedef long long LL;const int Max=1e5+10;LL A[Max];pair<LL,LL> B[Max*2];int main(){ int T; for(scanf("%d",&T);T;T--) { int n; LL L,R; scanf("%d%I64d%I64d",&n,&L,&R); for(int i=0;i<n;i++) { scanf("%I64d",&A[i]); } sort(A,A+n); int top=0; for(int i=1;i<n;i++) { B[top].first=A[i]-A[i-1]; B[top].second=-1; top++; B[top].first=A[i]+A[i-1]; B[top].second=1; top++; } sort(B,B+top); int count=0; LL pre=0,ans=0,dis,disr,disl; for(int i=0;i<top;i++) { if(count==0) { disr=min(R,B[i].first); disl=max(L,pre); dis=disr-disl+1; if(dis>=0) ans+=dis; } count+=B[i].second; pre=B[i].first; } disr=R;disl=max(L,pre); dis=disr-disl+1; if(dis>=0) ans+=dis; printf("%I64d\n",ans); } return 0;}
hdu 5720
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。