首页 > 试题广场 >

吃葡萄

[编程题]吃葡萄

热度指数：7103 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行数字，表示数据组数。
接下来行，每行三个数

输出描述:

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

示例1

输入

2
1 2 3
1 2 6

输出

2
3

示例2

输入

1
12 13 11

输出

算法知识视频讲解

天上白云蓝湛湛～

可以看成是三个人分别站在三角形的顶点（假定可以形成三角形）。设三角形两个短边是a,b，长边是c。则，若两短边之和大于等于长边的一半，可实现总数平分；反之，则结果为长边的一半。

最终结果为全部通过。

T = int(input())
for _ in range(T):
    x,y,z = map(int,input().split())
    food = [x,y,z]
    max_v,sum_v = max(food),sum(food)
    ans = 0
    if sum_v-max_v>=max_v//2:
        ans =(sum_v+2)//3
    else:
        ans = (max_v+1)//2
    print(ans)

发表于 2020-05-19 15:52:09 回复(3)

小厂大锅

python3

t=int(input())
for _ in range(t):
    a,b,c=map(int,input().split())
    maxnum=max(a,b,c)
    total=a+b+c
    if maxnum//2>=total-maxnum:
        if maxnum%2==0:
            print(maxnum//2)
        else:
            print((maxnum+1)//2)
    else:
        if total%3==0:
            print(total//3)
        elif total%3==1:
            print((total+2)//3)
        else:
            print((total+1)//3)

发表于 2020-04-07 18:33:27 回复(0)

SuHaoXD

把总和除以3向上取整，和最大的个数除以二向上取整，输出它们的最大值即可。

import sys 
T = int(sys.stdin.readline().strip())
data = []
for i in range(T):
    line = list(map(int,sys.stdin.readline().strip().split()))
    data.append(line)

res = []
for d in data:
    s = sum(d)
    m = max(d)
    a,b = divmod(s,3)
    c,d = divmod(m,2)
    a = a if b==0 else a+1
    c = c if d==0 else c+1
    res.append(max(a,c))

for i in res:
    print(i)

import sys 
T = int(sys.stdin.readline().strip())
data = []
for i in range(T):
    line = list(map(int,sys.stdin.readline().strip().split()))
    data.append(line)

res = []
for d in data:
    s = sum(d)
    m = max(d)
    a,b = divmod(s,3)
    c,d = divmod(m,2)
    a = a if b==0 else a+1
    c = c if d==0 else c+1
    res.append(max(a,c))

for i in res:
    print(i)

发表于 2020-08-08 00:38:42 回复(0)

牛客272529417号

python写的

a,b,c都是4位数时，第一组数据我的机器疯狂响了足有一分钟，然后结束任务，

现在的算法在葡萄数量级有10的18次方时可以在4秒运行完成吗？

看来我的功力差了不是一星半点啊，代码也不好意思发了

现在还在心痛我的电脑

发表于 2019-12-08 01:49:00 回复(0)

陈皮卡

python 3

代入几组尝试了一下找规律即可

n=int(input())
for i in range(n):
    a,b,c=map(int,input().split())
    maxn=max(a,b,c)
    total=a+b+c
    if maxn/2>(total-maxn):
        print(maxn//2+maxn%2)
    else:
        if (total%3==2):
            print(total//3+(total%3)//2)
        else:
            print(total//3+total%3)

发表于 2020-08-08 07:27:19 回复(0)

missingdaysqxy

平均5ms，412K占用

将一组三个葡萄数想像成三条线段，如果能构成三角形（符合两短相加大于长），则三个人一人吃掉相邻两条边的一半就可以；如果不能构成三角形（即有一超长边），那么要把超长边平分给两个人吃，相当于折断长边，现在有4条边肯定能构成四边形，那么有两种情况：

两个人吃完长边后不再吃短边，第三人吃完短边也没有超出另两个人；
两人吃完长边后，如果不帮第三人吃两个短边，会使第三人吃的超过2人。

第一种情况的输出就是长边的1/2；第二种情况则与三角形情况相同，需要所有人均分。
因此，综合来看只有两种情况：所有人平分，或者其中两人平分最多的那种葡萄。这两个哪个大，输出哪个。

#include <iostream>
#include <cmath>
using namespace std;
void sort(long list[3]) // 手动冒泡排序
{
    if (list[0]<list[1]) swap(list[0],list[1]);
    if (list[0]<list[2]) swap(list[0],list[2]);
    if (list[1]<list[2]) swap(list[1],list[2]);
}
 
int main()
{
    int n;
    long l[3], sum;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l[0] >> l[1] >> l[2];
        sort(l);
        sum = l[0] + l[1] + l[2];
        cout << max((sum + 2) / 3, (l[0] + 1) / 2) << endl;//加2与加1是为上取整
    }
}

编辑于 2019-12-16 21:40:40 回复(9)

王春招

难道不是贪心吗？先求总数的均值，每个人尽最大努力接近均值，此时最大值必然最小呀。

发表于 2020-07-01 23:25:03 回复(0)

冰镇的苦瓜

C, 2ms, 300KB

#include <stdio.h>

void getMaxSum(unsigned long long int* a, unsigned long long int* max, unsigned long long int* sum) {
    *max = 0;
    *sum = 0;
    for (unsigned int i = 0; i < 3; ++i) {
        *sum += a[i];
        if (*max < a[i]) {
            *max = a[i];
        }
    }
}

int main() {
    int T;
    unsigned long long a[3];
    scanf("%d", &T);
    while (T--) {
        while (scanf("%lld %lld %lld", &a[0], &a[1], &a[2]) != EOF) {
            unsigned long long M = 0, S = 0;
            getMaxSum(a, &M, &S);
            printf("%lld\n", (S + 2) / 3 > (M + 1) / 2 ? (S + 2) / 3 : (M + 1) / 2);
        }

    }
    return 0;
}

发表于 2024-05-24 08:51:25 回复(0)

牛客724266442号

//c#
public class Program
{
    public static void Main()
    {
        string line;
        while ((line = System.Console.ReadLine()) != null)
        {
            int[] nums = new int[int.Parse(line)];
            for (int a = 0; a < int.Parse(line); a++)
            {
                string[] tokens = System.Console.ReadLine().Split();
                nums[a] = Num(tokens);
            }
            foreach(var i in nums)
            {
                System.Console.WriteLine(i);
            }
        }
    }
    public static int Num(string[] str)
    {
        //排序
        Array.Sort(str);
        //三堆葡萄赋值
        int a = int.Parse(str[0]);
        int b = int.Parse(str[1]);
        int c = int.Parse(str[2]);

        if (a + b > c)
        {
            return (a + b + c + (3 - 1)) / 3;//向上取整（m + (n-1)）/n
        }
        if ((a + b) * 2 < c)
        {
            return (c + 1) / 2;
        }
        return (a + b + c + (3 - 1)) / 3;
    }
}

发表于 2023-08-31 19:00:17 回复(0)

YoJay

https://www.cnblogs.com/labuladong/p/13945545.html

发表于 2022-09-28 18:42:07 回复(0)

嘤之嘤

题目是不是有问题啊, 还是我搞错了

例如2 1 1时,最少是每人吃一个吧先2,后3再1

,所以输出一

而不是2吧

发表于 2022-05-12 20:32:05 回复(0)

ST_LZY

Code

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int m;
    cin>>m;
    vector<vector<long>> grapes(m,vector<long>(3,0));
    vector<long> sum(m,0);
    vector<long> res(m,0);

    for(int i=0; i<m; i++){
        for(int j=0; j<3; j++){
            cin >> grapes[i][j];
            sum[i] += grapes[i][j];
        }
        sort(grapes[i].begin(),grapes[i].end());
    }

    for(int i=0; i<m; i++){
        if(grapes[i][0] + grapes[i][1] > grapes[i][2]){
            res[i] = (sum[i]+2)/3;
        }
        else if(2 * (grapes[i][0] + grapes[i][1]) < grapes[i][2]){
            res[i] = (grapes[i][2] + 1)/2;
        }
        else{
            res[i] = (sum[i]+2)/3;
        }
        cout<<res[i]<<endl;
    }
}

发表于 2022-04-18 23:48:55 回复(0)

d东东

#include<vector>
#include<algorithm>
#include<iostream>
using std::vector;
using std::cout;
using std::cin;
using std::endl;
long test07(vector<long>&s)
{
    sort(s.begin(), s.end());
    long nums = s[0] + s[1] + s[2];
    if (s[0]+s[1]>s[2])
    {
        return (nums + 2) / 3;
    }
else
{
    if (s[2]>2*(s[0]+s[1]))
    {
        return (s[2] + 1) / 2;
    }
    else
    {
        return (nums + 2) / 3;
    }
}
}

int main() {

    vector<long> v1;
int n;
long l[3];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>l[0]>>l[1]>>l[2];
    v1.push_back(l[0]);
    v1.push_back(l[1]);
    v1.push_back(l[2]);
cout<<test07(v1)<<endl;
v1.clear();
}


    return 0;
}

发表于 2021-09-13 15:48:38 回复(0)

cloudKing

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

int main()
{
int T;
cin>>T;
while(T--)
{
long long arr[3],cursum;
cin>>arr[0]>>arr[1]>>arr[2];
cursum = arr[0] + arr[1] + arr[2];
sort(arr,arr+3);
if(arr[0] + arr[1] > arr[2])
cout<<(cursum + 2)/3<<endl;
else if(2*(arr[0] + arr[1]) < arr[2])
cout<<(arr[2] + 1)/2<<endl;
else
cout<<(cursum + 2)/3<<endl;

}
return 0;
}

发表于 2021-09-01 10:46:28 回复(0)

C/C++

牛客841529483号

因为一种水果是两个人吃，首先判断数量最多的水果数量是否是其它两种水果数量和的两倍，如果是，那这个水果必须两个人平分，剩下的两种水果由另一个人全吃掉，这样才能保证吃的多的人吃的尽量少，若是小于另外两种水果数量和的两倍，那最大值必是水果总量的三分之一，这里要判断总量能不能整除3，不能则要加1
#include <iostream>

using namespace std;

int main()
{
int T;
cin>>T;
while(T--)
{
long long p1,p2,p3;
cin>>p1>>p2>>p3;
long long a1=p1+p2+p3-max(max(p1,p2),p3);
long long a2=max(max(p1,p2),p3);
if(a1<(a2/2))
{
long long ave1=a2%2==0?a2/2:a2/2+1;
cout<<ave1<<endl;
}
else
{
long long ave=(p1+p2+p3)%3==0?(p1+p2+p3)/3:(p1+p2+p3)/3+1;
cout<<ave<<endl;
}
}
return 0;
}

发表于 2021-08-20 18:00:54 回复(0)

精通C++PythonGolang的拼写

import sys

def eat(a,b,c):
    sum_ = a+b+c
    max_ = max(a,b,c)
    return (max_+1)//2 if max_>2*(sum_-max_) else (sum_+2)//3
n = int(sys.stdin.readline())
for i in range(n):
    a,b,c=map(int,sys.stdin.readline().split(' '))
    print(eat(a,b,c))

发表于 2021-08-17 22:12:36 回复(0)

期末考试

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
long[] arr = new long[3];
for(int i = 0; i < count; i++){
long sum = 0;
long maxEgde = 0;
for(int j = 0; j < 3; j++){
if(sc.hasNextLong()){
arr[j] = sc.nextLong();
//maxEgde = Math.max(maxEgde, arr[j]);
sum = sum + arr[j];
}
}

//terminal shouji wanbi
Arrays.sort(arr);
if(arr[2] < arr[0] + arr[1]){
System.out.println((sum + 2)/3);
} else {

if(2 *(arr[0] + arr[1]) < arr[2]){
System.out.println((arr[2] + 1) /2);
} else {
System.out.println((sum + 2)/3);
}
}


}

}
}

import java.util.*;
public class Main { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        long[] arr = new long[3];
        for(int i = 0; i < count; i++){
            long sum = 0;
            long maxEgde = 0;
            for(int j = 0; j < 3; j++){
                if(sc.hasNextLong()){
                    arr[j] = sc.nextLong();
                    //maxEgde = Math.max(maxEgde, arr[j]);
                    sum = sum + arr[j];
                }
            }
                
                //terminal shouji wanbi
                Arrays.sort(arr);
                if(arr[2] < arr[0] + arr[1]){
                    System.out.println((sum + 2)/3);
                } else {
                    
                    if(2 *(arr[0] + arr[1]) < arr[2]){
                        System.out.println((arr[2] + 1) /2);
                    } else {
                         System.out.println((sum + 2)/3);
                    }
                }
            
            
        }
        
    }
}

发表于 2021-06-26 23:21:22 回复(0)

Mona432

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        long[] arr = new long[3];
        for(int i=0; i<count; i++) {
            long maxEdge = 0;
            long sum = 0;
            for(int j=0; j<3; j++) {
                if(sc.hasNextLong()) {
                    arr[j] = sc.nextLong();
                    maxEdge = Math.max(maxEdge, arr[j]);
                    sum += arr[j];
                }
            }
            //到此，terminal录入完毕，接下来开始处理计算录入数据

            //开始计算
            long avg = sum/3;
            if((sum - maxEdge) <= avg) {
                System.out.println((maxEdge+1)/2);
            } else {
                System.out.println((sum+2)/3);;
            }
        }
    }
}

模型：看作3段线首位连接组成到一个环，外加一个滑动窗口（以滑动窗口为卡尺）。

模型约束：窗口最多跨两段线。则最短的两条线段总长限制了该滑动窗口的最大值。

本题要实现吃得最多的人吃到的葡萄数量尽可能少，最理想的情况就是尽可能平分总葡萄数，即为滑动窗口的理想大小。所以，只要最小的两条线段长度和大于3条线段总长的平均长度，则滑动窗口就一定能理想整数等分该环。

而，如果输入无法满足滑动窗口大小理想化，即最短两边和小于等于环长的三分之一，则只有将剩下的长度尽可能整数二等分。分得等两个中较大的即为所求。

发表于 2021-03-05 21:11:37 回复(0)

JavaScript

牛客562036433号

/**
  * JavaScript版本
 * 考虑，尽可能平均地分配葡萄，才能让吃的多的人吃的最少。而/_\a,b,c可以组成一个三角形，当然如果c边过大，那么考虑将c分成两段。
 * 取最长边设置为c
 * 情况一：a+b>c,那么只要找到a,b,c边的中点即可平分，但有可能不能整除，用Math.ceil()向上取整
 * 情况二：a+b<=c, 若c>2*(a+b),那么只要取c的中点，否则还是可以去a,b,c三者中点，向上取整即可。
 */
let input = [];
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

function solution(input){
    let n = parseInt(input[0]);
    let res = [];
    for(let i=1;i<n+1;i++){
        let arr = input[i].split(' ').map(x=>parseInt(x));
        arr.sort((a,b)=>(a>b)?1:a<b?-1:0);
        let a = arr[0], b = arr[1], c = arr[2];
        console.log(ave(a,b,c));
    }
}

function ave(a,b,c){
    let sum  = a + b + c;
    if(a+b>c){
    //res.push(Math.ceil(sum/3));
        return Math.ceil(sum/3);
    }
    if(c>2*(a+b)){
         return Math.ceil(c/2);
    }
    return Math.ceil(sum/3);
}

rl.on('line',line=>{
    input.push(line);
    let n = parseInt(input[0]);
    if(input.length===n+1){
        solution(input);
    }
})

/***************************************************************************/
// 使用BigInt来解决Number越界问题

	let input = [];
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout 
})
function solution(input){
    let n = parseInt(input[0]);
    // console.log(input); 
    // console.log(2**53 - 1); 
    for(let i=1;i<n+1;i++){
        let arr = input[i].split(' ').map(x=>BigInt(x));
        arr.sort((a,b)=>(a>b)?1:a<b?-1:0);
        let a = arr[0], b = arr[1], c = arr[2];
        console.log(ave(a,b,c).toString());
    }
}
function ave(a,b,c){
    let sum  = a + b + c;
    // console.log(a,b,c,a+b,a+b>c); 
    if(a+b>c){
    //res.push(Math.ceil(sum/3)); 
        return (sum + 2n) / 3n;
    }
    if(c>2n*(a+b)){
         return (c+1n)/ 2n;
    }
    return (sum+2n) / 3n;
}
rl.on('line',line=>{
    input.push(line);
    let n = parseInt(input[0]);
    if(input.length===n+1){
        solution(input);
    }
})

编辑于 2021-01-30 13:45:29 回复(0)

牛客904399584号

借鉴君の名は20180109105787的解题思路，在第一个判定发现另一个等价的判定条件

t=int(input())
for _ in range(t):
    a,b,c=map(int,input().split())
    maxnum=max(a,b,c)
    total=a+b+c
    if maxnum>2*(total//3):
        if maxnum%2==0:
            print(maxnum//2)
        else:
            print((maxnum+1)//2)
    else:
        if total%3==0:
            print(total//3)
        elif total%3==1:
            print((total+2)//3)
        else:
            print((total+1)//3)

发表于 2020-09-26 00:08:01 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师网易算法工程师测试开发工程师安全工程师 2020 数据分析师 Java工程师

上传者：小小

难度：

25条回答 229收藏 16183浏览

通过挑战的用户

牛客31324...

2023-03-07 17:12:54
牛客78739...

2023-03-06 09:18:15
猫叮叮

2023-02-10 14:32:00
国企上岸了的秋...

2023-02-08 09:13:57
牛客21827...

2023-01-30 15:35:45

吃葡萄

输入描述:

输出描述:

输入

输出

输入

输出

Code

问题信息

热门推荐

通过挑战的用户

相关试题