题意：给定A,B,C,D四个数，
A≤x≤B≤y≤C≤z≤D
让我们求出符合条件的三角形的个数
思路：可以通过枚举一条边，其余两条通过计算来获得
具体做法为：枚举一条边，然后将第二条边先定为最大值(即C)，然后看看当前的情况能够拿（C，D）范围内的边来凑
假如A B C D 分别为 3 6 9 11
那么在第一次枚举的时候，我们先定第一、二条边为3，9 那么第三条边可以选取的范围为【9，11】即3个数，标记为sto
这个时候我们再看看第二条边可以选取的范围【6，7，8，9】
列举一下可知，当x==3时，有3 + 2 + 1=6种选取方式
也就是说当第二条边的范围大于等于sto时，我们就有sto*(sto+1)/2种选法
具体思路大致如此
但是，有一些特殊情况
（1）当枚举第一条边的数值大于第三条边的选取范围时，我们改一下上面的例子，改为 5 6 9 11
那么当x==5时，有3+3+3种选取方式
（2）当出现第二条边的选取范围小于sto时，计算方式改为 sto*(sto+1)/2-(base[limit]) //具体情况看代码
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=5e5+10; 5 ll base[maxn]; 6 void init() 7 { 8 for(int i=1;i<=maxn-5;i++){ 9 base[i]+=base[i-1]+i; 10 } 11 } 12 int main() 13 { 14 init(); 15 ll A,B,C,D; 16 scanf("%lld%lld%lld%lld",&A,&B,&C,&D); 17 ll ans=0; 18 ll sto=0; 19 for(ll i=A;i<=B;i++){ 20 ll tmpa=i; ll tmpb=D-C+1; 21 sto=tmpb; 22 if(tmpa<=tmpb){ 23 //还需看看第二条边有多少种可能 24 ll limit=tmpa-(C-B+1); 25 if(limit<0) limit=0; 26 ans+=tmpa*(tmpa+1)/2; 27 ans-=base[limit]; 28 } 29 else{ 30 ll sum=tmpa-tmpb; 31 ll total=C-B+1; 32 if(sum>=(total-1)){ 33 ans+=total*sto; 34 } 35 else{ 36 ans+=sto*sum+sto*(sto+1)/2; 37 ll limit=sto-total+sum; 38 if(limit<0) limit=0; 39 ans-=base[limit]; 40 } 41 } 42 } 43 printf("%lld\n",ans); 44 return 0; 45 }
原文链接: https://www.cnblogs.com/pangbi/p/13323476.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367214
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
