FZU-2127-养鸡场

G - 养鸡场
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit

Status

Practice

FZU 2127
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

枚举第一个区间，然后求出第二条边的左右边界，同时注意三角形三边关系。如果左右边界之前还有整数点，那就是三角形数量了

还一个思路就是高中学的线性规划，一条边枚举，另两条可以看成一条直线，接着就是求给定区间相交范围内的整数点数量，虽然好想，但是太麻烦，最后采用的还是第一种思路

代码

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{int n;while(~scanf("%d",&n)){int x1,y1,x2,y2,x3,y3;scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);int sum=0;//初始化数量for(int i=x1; i<=y1; i++)//i看成一条边，枚举即可{int flag=max(i,max(x2,n-y3-i));//寻找第二条边的左边界flag=max(flag,n/2-i+1);//还要满足三角形三边关系int temp=min(y2,n-x3-i);//第二条边的右边界temp=min((n-i)/2,temp);//还要满足三角形三边关系if((temp-flag+1)>0)//左右边界之间还有空位sum+=temp-flag+1;//空位就是数量}printf("%d\n",sum);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！