hdu_5720_Wool(脑洞)

题目连接：hdu_5720_Wool

题意：

给你N个数，然后给你一个区间，问你在这个区间内有多少数可以不与这N个数任选两个出来组成三角形

题解：

这里我还是贴官方的题解算了

考虑三角形三条边 $a, b, c$ $(a \geq b)$ 的关系 $a - b < c, a + b > c$ ，即 $c \in (a - b, a + b)$ 。

令加入的边为 $c$ ，枚举所有边作为 $a$ 的情况。对于所有可行的 $b$ ，显然与 $a$ 相差最小的可以让 $(a - b, a + b)$ 覆盖范围最大，所以可以贪心地选择不大于 $a$ 的最大的 $b$ 。

于是我们可以先将边按长度排序，然后 $a_i$ 和 $a_{i + 1}$ 建一条线段。线段并是不合法的部分。

将所有线段按左端点排序，按序扫描一遍，过程中统计答案即可。

时间复杂度 $O (T n lo g n)$ 。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define F(i,a,b) for(int i=a;i<=b;i++)
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<LL,LL>P;
 7 
 8 const int N=1e5+7;
 9 LL a[N],l,r;
10 P sq[N];
11 int main(){
12     int t,n;
13     scanf("%d",&t);
14     while(t--){
15         scanf("%d%lld%lld",&n,&l,&r);
16         F(i,1,n)scanf("%lld",a+i);
17         sort(a+1,a+1+n);
18         F(i,1,n-1){
19             sq[i].first=a[i+1]-a[i];
20             sq[i].second=a[i]+a[i+1];
21         }
22         sort(sq+1,sq+n);
23         LL ans=0;
24         F(i,1,n-1){
25             if(sq[i].second<=l)continue;
26             if(sq[i].first>r)break;
27             if(sq[i].first>=l)ans+=sq[i].first-l+1;
28             l=sq[i].second;
29             if(l>r)break;
30         }
31         if(l<=r)ans+=r-l+1;
32         printf("%lld
",ans);
33     }
34     return 0;
35 }

View Code