FZU 2127 养鸡场

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

3 5

Sample Output

Source

福州大学第十届程序设计竞赛

#include <stdio.h>

#include <algorithm>

using namespace std;

/*思路 ： 先确定第一条边（枚举）, 然后 确定 第二条边 的变化范围 ，

要注意 题目的限制条件及边的范围，同时要满足构成 三角形的条件 ，

即两边之和大于第三边。确定完第二条边 ,后确定第三条边的变化范围 ，

最后 ans=min(第二条边变化范围,第三条边变化范围).*/

int main()

{

    int n,i;

    int l[], r[];

    while (scanf("%d", &n) == )

    {

        for (i= ; i < ; i++) scanf("%d%d", l+i, r+i);

        int ans=;

        for (int i=l[]; i<=r[]; i++)

        {

            int tmp=(n-i)/;

            if (tmp<i) break;

            int min1=max(l[], i);

            min1=max(min1, n/-i +);

            int max1=min(r[], tmp);

            int min2=max(l[], tmp+(((n-i) %  == ) ?  : ));

            int max2=min(r[], n-i-min1);

            tmp=min(max1-min1+, max2-min2+);

            if (tmp>) ans += tmp;

        }

        printf("%d\n", ans);

    }

    return ;

}

数论推理

秒客网