Problem 2127 养鸡场 Accept: 59 Submit: 211Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Jason买来了n米长的竹篱笆，打算将n米长的竹篱笆全部用来围成一个三角形的养鸡场。为方便起见，养鸡场三条边的长度都为正整数。同时，他想让自己的养鸡场看起来更美观一些，要求三条边的长度分别在一个区间范围内。
现在，他想知道有多少种不同的方案使得围成的养鸡场满足要求？
Input
输入包含多组数据。输入数据第一行是一个正整数n，表示竹篱笆的长度。
在接下来三行中，第i行的两个正整数为xi，yi。表示三角形的第i条边的边长ai的范围在[xi,yi]内。
注意：Jason规定a1≤a2≤a3。
Output
输出一个整数，表示满足要求的不同方案数。
约定：
对于第二行至第四行，都有1≤xi≤yi ≤n
对于50%的数据n≤5000
对于100%的数据n≤200000
Sample Input
12 3 5 3 5 3 5
Sample Output
2
Source
福州大学第十届程序设计竞赛 // 直接枚举明显是不行的，因为x+y+z == n 所以我们可以枚举x ，// 然后 y = n-z-x ； 又 y >= x && y <= z ； 还有 x2 <= y <= y2 // 还要满足三角形 y-x < z < y+x ，由上可以求出 z 的范围 最后还要满足 x3 <= z <= y3 #include#include #include #include #include #include #include #define maxn 100002#define LL long longusing namespace std ;int min1( int a , int b ){ return a < b ? a : b ;}int main(){ int i ,k ,j ,t1,t2 ; int n , m , ans , L1 , L2 , R1 , R2 ; int x1 , x2 ,x3 , y1 , y2 ,y3 ; // freopen("in.txt","r",stdin) ; while( scanf("%d",&n) != EOF ) { scanf("%d%d" , &x1 , &y1 ) ; scanf("%d%d" , &x2 , &y2 ) ; scanf("%d%d" , &x3 , &y3 ) ; ans = 0 ; for( int x = x1 ; x <= y1 ;x++ ) { L1 = (n-x*2)/2+1; if(n&1) R1 = n/2 ;// 这里要注意 else R1 = n/2-1 ; L2 = n-x-y2 ; R2 = n-x-x2 ;// L1 = max(L1,L2) ; R1 = min1(R1,R2) ; L1 = max(L1,(n-x+1)/2) ; R1 = min1(R1,n-x*2) ;// 原来(n-x)/2 ，这里也是要奇偶，改成(n-x+1)/2 就不用了 L1 = max(L1,x3) ; R1 = min1(R1,y3) ; ans += max(0,R1-L1+1) ;// 要判断正负 } printf("%d\n",ans) ; } return 0 ;}