几何问题

✏️ 1、利用几何性质解决问题

有三种葡萄,每种分别有a、b、c颗。有三个人,第一个人只吃第1、2种葡萄,第二个人只吃第2、3种葡萄,第三个人只吃第1、3种葡萄。适当安排三个人使得吃完所有的葡萄,并且且三个人中吃的最多的那个人吃得尽量少。

输入描述:

  • 第一行数字 T\mathit T ,表示数据组数。

  • 接下来 T\mathit T 行,每行三个数 a,b,c\mathit a,b,c

  • 1a,b,c1018,1T101 \leq a,b,c \leq 10^{18} , 1 \leq T \leq 10

输出描述:

对于每组数据,输出一行一个数字表示三个人中吃的最多的那个人吃的数量。

先不管每个人只能吃两种特定葡萄的约束,你怎么让「吃得最多的那个人吃得最少」?显然,只要平均分就行了,每个人吃(a+b+c)/3颗葡萄。即便不能整除,比如说a+b+c=8,那也要尽可能平均分,就是说一个人吃 2 颗,另两个人吃 3 颗。

综上,「吃得最多的那个人吃得最少」就是让我们尽可能地平均分配,而吃的最多的那个人吃掉的葡萄颗数就是(a+b+c)/3向上取整的结果,也就是(a+b+c+2)/3

PS:向上取整是一个常用的算法技巧。大部分编程语言中,如果你想计算M除以NM / N会向下取整,你想向上取整的话,可以改成(M+(N-1)) / N

现在考虑一下如果加上「每个人只能吃特定两种葡萄」的限制,怎么做?也就是说,每个人只能吃特定两种葡萄,你也要尽可能给三个人平均分配,这样才能使得吃得最多的那个人吃得最少。

这可复杂了,如果用X, Y, Z表示这三个人,就会发现他们组成一个三角关系:

如果把葡萄的颗数a, b, c作为三条线段,它们的大小作为线段的长度,想一想它们可能组成什么几何图形?我们的目的是否可以转化成「尽可能平分这个几何图形的周长」?

三条线段组成的图形,那不就是三角形嘛?不急,我们小学就学过,三角形是要满足两边之和大于第三边的,假设a < b < c,那么有下面两种情况:

如果a + b > c,那么可以构成一个三角形,只要取每条边的中点,就一定可以把这个三角形的周长平分成三份,且每一份都包含两条边:

也就是说,这种情况下,三个人依然是可以平均分配所有葡萄的,吃的最多的人最少可以吃到的葡萄颗数依然是(a+b+c+2)/3

如果a + b <= c,这三条边就不能组成一个封闭的图形了,那么我们可以将最长边c「折断」,也就是形成一个四边形。

这里面有两种情况:

对于情况一,a + bc的差距还不大的时候,可以看到依然能够让三个人平分这个四边形,那么吃的最多的人最少可以吃到的葡萄颗数依然是(a+b+c+2)/3

随着c的不断增大,就会出现情况二,此时c > 2*(a+b),由于每个人口味的限制,X顶多吃完ab,为了尽可能平分,c边需要被YZ平分,也就是说此时吃的最多的人最少可以吃到的葡萄颗数就是(c+1)/2,即平分c边向上取整。

int main()
{
    int T = 0;
    long long a = 0, b = 0, c = 0;
    cin >> T;
    while(T > 0){
        cin >> a >> b >> c;
        long long temp = 0;
        if(a>b) temp = a, a = b, b = temp;
        if(b>c) temp = b, b = c, c = temp;
        if(a>b) temp = a, a = b, b = temp;
        if(c > 2 * (a + b)){
            cout << (c + 1) / 2 << endl;
        }else{
            cout << (a + b + c + 2) / 3 << endl;
        }
        --T;
    }
    return 0;
}

✏️ 2、解决几何问题

给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。

最后更新于

这有帮助吗?