首页 > 试题广场 >

切割块

[编程题]切割块

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

有一个x*y*z的立方体，要在这个立方体上砍k刀，每一刀可以看作是用一个平行于立方体某一面的平面切割立方体，且必须在坐标为整数的位置切割，如在x=0.5处用平面切割是非法的。

问在切割k刀之后，最多可以把立方体切割成多少块。

输入描述:

输入仅包含一行，一行包含4个正整数x,y,z,k分别表示x*y*z的立方体和切割k刀。（1<=x,y,z<=10^6,0<=k<=10^9）

输出描述:

输出仅包含一个正整数，即至多切割成多少块。

示例1

输入

2 2 2 3

输出

算法知识视频讲解

NB新手玩家

思路，由于必须按整数来切，所以
max快=x*y*z，实际就是体积的大小
max刀=(x-1)+(y-1)+(z-1)，就是保证切出来的==立方体体积最小=1==边长为3就要切2刀
2*2*2* 切3刀=8快
2*2*2* 切2刀=几快？
这需要在某一个边上少切一刀，是那一条边？（实践证明是最长的那条边）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[5],k;
    long long int maxd,maxk,m=104909296875;
    scanf("%d%d%d%d",&a[1],&a[2],&a[3],&k);
     //刀数
    maxd=(long long int)(a[1]-1)+(a[2]-1)+(a[3]-1);
     //快数
    maxk=(long long int)a[1]*a[2]*a[3];
    //k超过刀数
    if(k>=maxd)
    {
        printf("%lld\n",maxk);
        return 0;
    }
    else while(maxd!=k)
    {
        //找最长的那条边
        sort(a+1,a+4);
        //最长边减1
        a[3]--;
        //新的刀数和快数
        maxd=(long long int)(a[1]-1)+(a[2]-1)+(a[3]-1);
        maxk=(long long int)a[1]*a[2]*a[3];
    }
    printf("%lld",maxk);
    return 0;
}

发表于 2020-02-13 09:46:16 回复(0)

Java

One-Punce-Man

import java.util.Arrays;
import java.util.Scanner;
public class Main{
 
    private long a = 1;
    private long b = 1;
    private long c = 1;
 
 
 
    // 排序解决方案：
    public  long func(int x,int y ,int z, int k){
        int arry[] =  {x,y,z};
        Arrays.sort(arry);
        //System.out.println(arry);
        int size =k +1;
        int i;
        for(i = 0;i < k;){
 
 
            if(a < arry[0] && a == b)   {
                a++;
                i++;
            }
 
            else if(c < arry[1] &&  c == b)   {
                c++;
                i++;
            }
            else if(b < arry[2]) {
                b++;
                i++;
            }
            else break;
        }
        return a * b * c;
    }
 
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main main = new Main();
        while (in.hasNextInt()) {//注意while处理多个case              int a = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            int k = in.nextInt();
            System.out.println(main.func(x,y,z,k));
        }
 
    }
}

java实现，供参考。

发表于 2020-02-19 23:48:42 回复(0)

scent-wen

#include<iostream>
(720)#include<algorithm>
using namespace std;

void solve1030() {
    int x, y, z;
    while (cin >> x >> y >> z) {
        int times; cin >> times;
        long long  x_cnt=1, y_cnt =1, z_cnt =1; //int 会溢出
        long f = 0;
        while (times-- > 0) {
            if (x == 1 && y == 1 && z == 1) break;

            if (x > 1 && f == 0) { x -= 1; x_cnt += 1; }
            else if (y > 1 && f == 1) { y -= 1; y_cnt += 1;}
            else if (z > 1 && f == 2) { z -= 1; z_cnt += 1;}    
            else {
                times++;
            }
            f += 1; f %= 3; // 轮询切菜
        }

        cout << x_cnt * y_cnt * z_cnt << endl;
    }
}

int main(){
    solve1030();
    return 0;
}

发表于 2020-03-13 12:10:10 回复(0)

找个工作也太难了

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long[] len=new long[3];
        len[0]=sc.nextLong();
        len[1]=sc.nextLong();
        len[2]=sc.nextLong();
        long k=sc.nextLong();
        Arrays.sort(len);
        long temp=k/3;
        long c0=Math.min(len[0]-1,temp);
        k=k-c0;
        temp=k/2;
        long c1=Math.min(len[1]-1,temp);
        k=k-c1;
        long c2=Math.min(len[2]-1,k);
        System.out.println((c0+1)*(c1+1)*(c2+1));
    }
}

发表于 2021-07-18 08:38:45 回复(0)

Silence丶2

可以x+y+z = cons,求x*y*z的最大值，以边界求解最值，代码复杂可为O(1)：

x,y,z,k = list(map(int,input().split()))

class solution:
    def __init__(self,x,y,z):
        f = [x,y,z]
        f.sort()
        self.x,self.y,self.z = f
    def fun(self,k):
        xx = k // 3 + 1
        yy = k // 3 + 1
        zz = k // 3 + 1
        NN = k%3
        shengxia = NN
        if xx > self.x:
            shengxia += xx - self.x
            xx = self.x

        if yy > self.y:
            shengxia += yy - self.y
            yy = self.y
        elif shengxia != 0 and yy+shengxia//2 < self.y:
            yy += shengxia //2
            shengxia = shengxia - shengxia //2
        elif shengxia != 0:
            shengxia = shengxia - (self.y - yy)
            yy = self.y
        if zz > self.z:
            zz = self.z
        if shengxia != 0:
            zz += shengxia
            if zz>self.z:
                zz = self.z
        return xx*zz*yy
fun = solution(x,y,z)
print(fun.fun(k))

发表于 2020-08-14 20:35:25 回复(0)

牛客237407020号

#include<cstdio>
(802)#include<cstring>
#include<iostream>
(720)#include<algorithm>
using namespace std;
int main()
{
    int a[5],k;
    long long int maxd,maxk,m=104909296875;
    scanf("%d%d%d%d",&a[1],&a[2],&a[3],&k);
     //刀数
    maxd=(long long int)(a[1]-1)+(a[2]-1)+(a[3]-1);
     //快数
    maxk=(long long int)a[1]*a[2]*a[3];
    //k超过刀数
    if(k>=maxd)
    {
        printf("%lld\n",maxk);
        return 0;
    }
    else while(maxd!=k)
    {
        //找最长的那条边
        sort(a+1,a+4);
        //最长边减1
        a[3]--;
        //新的刀数和快数
        maxd=(long long int)(a[1]-1)+(a[2]-1)+(a[3]-1);
        maxk=(long long int)a[1]*a[2]*a[3];
    }
    printf("%lld",maxk);
    return 0;
}

发表于 2020-03-12 06:39:38 回复(0)

许愿一个offer啊

var a = readline().split(' ')
var x = parseInt(a[0])
var y = parseInt(a[1])
var z = parseInt(a[2])
var k = parseInt(a[3])
main(x,y,z,k)
function main(x,y,z,k){
    var a = [x,y,z]
     
    var max
    var max_kuai =a[0]*a[1]*a[2]
    var max_dao = a[0]+a[1]+a[2]-3
    if(k>=max_dao){
        max = max_kuai
    }else{
        while(max_dao !== k){
            a.sort(sortnumber)
            a[2]--
            max_dao = a[0]+a[1]+a[2]-3
            max_kuai = a[0]*a[1]*a[2]
        }
        max = max_kuai
    }
    return console.log(max)
}
function sortnumber(a,b){
    return a-b
}

发表于 2020-02-25 16:18:58 回复(0)

牛客481733148号

x, y, z, k = [int(x) for x in input().split(' ')]
x, y, z = sorted([x-1, y-1, z-1])

if x*3 >= k:
    x = y = int(k/3)
    z = k - x - y
else:
    y = min(int((k - x)/2), y)
    z = min((k - x - y), z)

max_chunks = (x+1)*(y+1)*(z+1)
print(max_chunks)

理想情况肯定是均匀切k/3刀,

如果最短边不够的话就先切满, 剩下两条边争取均匀切剩下的刀,

再不行就没得选了

编辑于 2020-09-13 00:36:33 回复(1)

牛客533742469号

data = list(map(int,input().split(" ")))
k = data.pop()
def cut(data,k):
cut_k = 0
if data[0]+data[1]+data[2]-3 <= k:
cut_k = data[0]*data[1]*data[2]
else:
while data[0]+data[1]+data[2]-3 != k:
data.sort()
data[-1] -= 1
cut_k = data[0]*data[1]*data[2]
return cut_k
print(cut(data,k))

发表于 2020-07-02 20:42:19 回复(0)

Java

JAVA_NINA

代码

package org.nina.learn.aqy;

import java.util.Scanner;

/**
 * @Author: zgc
 * @Description: 切割块
 * @Date: 2020/4/17 0:17
 * @Version: 1.0
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in = sc.nextLine();
        String[] inputs = in.split(" ");
        long x = Integer.valueOf(inputs[0]);
        long y = Integer.valueOf(inputs[1]);
        long z = Integer.valueOf(inputs[2]);
        long k = Integer.valueOf(inputs[3]);
        Main main = new Main();
        System.out.println(main.split(x, y, z, k));
    }

    public long split(long x, long y, long z, long k) {
        if (k == 0) {
            return 1;
        }
        long a = 1, b = 1, c = 1;
        while (k > 0 && a + b + c < x + y + z) {
            if (a < x && k > 0) {
                a ++;
                k --;
            }
            if (b < y && k > 0) {
                b ++;
                k --;
            }
            if (c < z && k > 0) {
                c ++;
                k --;
            }
        }
        return a * b * c;
    }


}

思路

首先，三个轴，每个轴在不切的情况下都是1等分。这里假设a对应x轴的等分数，那么不切的情况下a=1,以后每切1刀x轴对应的等分数为a = a + 1。同理假设b对应y轴，那么每切1刀y轴对应的等分数为b = b + 1。同理假设c对应z轴，那么每切1刀z轴对应的等分数为c = c + 1。
其次，不管是x轴、y轴还是z轴，每切1刀，刀数都会减1，为了得到最大的块数，必须连续的3刀切割在不同的轴上。

注意

这里应该使用long类型，而不应该使用int类型。long类型的最大值为2^64-1=9223372036854775807。int类型的最大值为2^32-1=2147483647。而 1<=x,y,z<=10^6,0<=k<=10^9。如果用int类型，得到的结果可能超出int类型的最大值，高出32位的数会被截掉，只留下剩下的32位的int值，这样就会出错。因此一定要用long型。

编辑于 2020-04-22 23:40:26 回复(0)

吃**的蜗牛

//排序，尽量平衡分刀
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int nums[] = new int[3];
		int res[] = new int[3];
		long ans = 1;
		Scanner input = new Scanner(System.in);
		for (int i = 0; i < nums.length; i++) {
			nums[i] = input.nextInt();
		}
		Arrays.sort(nums);
		int k = input.nextInt();
		for (int i = 0; i < 3; i++) {
			int cut = k / (3 - i);
			if (cut > nums[i] - 1) {
				res[i] = nums[i];
			} else {
				res[i] = cut + 1;
			}
			k = k - (res[i] - 1);
			ans = ans * res[i];
		}
		
		System.out.println(ans);
	}
}

发表于 2020-04-14 23:35:13 回复(0)

火力全开201909070000744

#include<iostream>
using namespace std;
int main()
{
    long long int x;
    long long int y;
    long long int z;
    long long int k;
    cin>>x>>y>>z>>k;
    long long int x_=0;
    long long int y_=0;
    long long int z_=0;
    long long int m = min(k,(x+y+z-3));
    for(int i =1 ;i<=m;i++)
    {
        if (x_==x-1)
            x_=1e10;
        if (y_==y-1)
            y_=1e10;
        if (z_==z-1)
            z_=1e10;
        long long int* p = &x_;
        if (*p>=y_)
            p=&y_;
        if(*p>=z_)
            p=&z_;
        *p=*p+1;
    }
    if(x_==1e10)
        x_=x-1;
    if(y_==1e10)
        y_=y-1;
    if(z_==1e10)
        z_=z-1;
    cout<<(x_+1)*(y_+1)*(z_+1)<<endl;
         
     
}

发表于 2020-03-25 20:44:47 回复(0)