网易2020校招笔试- 运维工程师（正式批）编程题 吃葡萄

【说点啥】

代码题不难，第一题思维或者二分，第二题dp，第三题离散化+二分，第四题贪心。（理论题gg

第一题思维一下没想到，所以写一下题解。

题面：

思路：一看数据这么大有1e18肯定是思维题，再一看答案具有单调性直接二分答案。

二分的check函数这么写：如果最多的葡萄都可以被吃完，那么最少和次少一人负责一款直接解决就好了；如果两个人都吃不完最多的葡萄，那么这个肯定有得剩吃不完；否则轮流按优先吃最多、然后次少、判断剩下的能不能被最后一个人吃完。

二分时间复杂度是logn级别的，因此这种写法的时间复杂度最多是log(1e18)也就是64，相当于常数级别看作O(1)。

另一种解法：思维

当 a,b,c都差不多大 或者 其中两个比较大的时候，我们总能调整到尽可能平均；当其中一个比较大的时候，由于这个只能被两个人吃掉，所以最好也是对半分。所以答案就是：三个人平均分配 a,b,c 或者 两个人分配最多的数目的最大值。

代码：

// 二分
#include <bits/stdc++.h>
using namespace std;

bool check(long long num,long long a[]){
    if (a[2]<=num) {
        return true;
    }
    if (a[2]-num>num) {
        return false;
    }
    return a[0]+a[1]+a[2]-2*num<=num;
}
 
int main()
{
    int t; cin>>t;
    while(t--){
        long long a[3];
        for(int i=0;i<3;i++)
            cin>>a[i];
        sort(a,a+3);
        long long l=1,r=(long long)1e18;
        long long mid,ans;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid,a)){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

// 思维
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t; cin>>t;
    while(t--){
        long long a[3];
        long long sum=0;
        for(int i=0;i<3;i++)
            cin>>a[i],sum+=a[i];
        sort(a,a+3);
        cout<<max((sum+2)/3,(a[2]+1)/2)<<endl;
    }
    return 0;
}