漫画:有趣的 “切蛋糕“ 问题
大数据DT
共 7738字,需浏览 16分钟
·
2022-06-12 21:13
导读:一道又烧脑又有趣的ACM比赛题目。
![](https://filescdn.proginn.com/1a8ef62fcc5afc11d7f918229a4b0969/fda1cec693311c9a586820d53d2854e8.webp)
![](https://filescdn.proginn.com/9094059a7fc0803f18f420be958a2548/c46d5505fe63ddc402eab86dc25897a1.webp)
![](https://filescdn.proginn.com/9fec59b69a4871a3127f235ae1699436/bd00266fa9029ff2bbad2c14397f87b3.webp)
![](https://filescdn.proginn.com/d162f60c5607a1da938c7e56cea1a786/ec3e29b003d238e439199943e2832727.webp)
![](https://filescdn.proginn.com/4759be65527661dae62dfdfdab38f4b3/6251782da59d9e855b5258ec5d45a0ac.webp)
![](https://filescdn.proginn.com/d73391e8d9cbee0c71b721745c5cf957/ceb96c3aa62a220a76df542df99511d8.webp)
![](https://filescdn.proginn.com/0c3babc7c6cb76bc91981d309d5da8fa/03230ddec0f6dfb1f3b3a9bf1e9bd635.webp)
![](https://filescdn.proginn.com/225d0bffc0b51aa4eae56fefd36468af/04810e3091c007d244f5c3fa5fc32ebb.webp)
![](https://filescdn.proginn.com/b51ef0903938a20a3b003494f1b38ad0/cba932794d33aeeac63e7d53364edb66.webp)
比如:输入cakes集合 {2,9};输入mouths集合 {5,4, 2,8} 正确返回:3
![](https://filescdn.proginn.com/9f291baa4f35a278f0c443ebb3a680e8/c0209c178d0c341173849ed3f7d82864.webp)
![](https://filescdn.proginn.com/417b6803eff32dd28e9f4aa6633eb27c/e114ecbba499e488b94f50c640d04866.webp)
![](https://filescdn.proginn.com/ef554bbf89c5e14182790ce149968048/d641bb13c3f21993db7e4151149975a6.webp)
![](https://filescdn.proginn.com/edbe7831cf20153d27e228733309c26c/ae35d52395deb06d0d44393ed5ce8d2c.webp)
![](https://filescdn.proginn.com/5a8559da09de5125be81bfe7fb9ec63f/58483a2fe03e6bf71c960f87d94b054c.webp)
![](https://filescdn.proginn.com/fd34886b04d8790ad2de433fe367d7b6/a65670dbad2e90a8637b39463ec2e25d.webp)
![](https://filescdn.proginn.com/bd35ac8048f71a06a3c3de86c73fad6c/aba2954d3d549427cf8fefa7523b5e37.webp)
![](https://filescdn.proginn.com/ffa6b651a76530edcf0b3eca58174e59/70e966cd46a59fbeec720596840c89b0.webp)
![](https://filescdn.proginn.com/1990f7d7665fb3e9ef0c4c93e2f07290/ade82ccd17c9216d182dc8f8a0e05a24.webp)
![](https://filescdn.proginn.com/25976d68e675a96d56efb5a8012afb67/d51279b7a15ea281462e90b6c2f3a08d.webp)
![](https://filescdn.proginn.com/648b1fabb57767963c834a2e88ce7917/bf6237589ed3930a0c90600691a3c65a.webp)
![](https://filescdn.proginn.com/3e133527d70c94149b504373644d869e/4da8bece2ac88137638bdcd33c1a448b.webp)
3的蛋糕满足2的顾客, 5的蛋糕满足5的顾客, 15的蛋糕满足12的顾客, 17的蛋糕满足7和9的顾客, 25的蛋糕满足14的顾客。
![](https://filescdn.proginn.com/6c644cf44c7eff62f42320806e79cbf2/04009863de92b737b1acbb912aeedb86.webp)
![](https://filescdn.proginn.com/1040780de6ec26bd6127a7182868c0cb/7ed797708da8cf189ff347d12694a2c1.webp)
![](https://filescdn.proginn.com/6c5920bfdc3dfa81d0bb1455fe110d85/1eedf91e111dabc83789687798faa928.webp)
![](https://filescdn.proginn.com/7dc3fe0faae71fd6a3cb0563eb34596f/bde702e25d4635a29b069f3174ff5af8.webp)
![](https://filescdn.proginn.com/a552cafbc51755ec37d93d4d46fcdfdf/f6896f114bfe6a02703c07be9cf4cd83.webp)
![](https://filescdn.proginn.com/12b56b4b59a6072b53d6609e1aaeb578/f657d78901ddb4c9959bae96a5e72ad7.webp)
![](https://filescdn.proginn.com/31133ce25d2d24b3a36ab197ac4dba55/9b7fc99fcc09e098f5a4fb4ebd7f83b8.webp)
![](https://filescdn.proginn.com/69c2b1c6d53a59a6b188e1b668e45d88/789bc796c414ea87034affe647919b0b.webp)
![](https://filescdn.proginn.com/b3fd709bfecea1888e3af9ba77f2df36/b39b83344ed20daad4e70212a6a1b73e.webp)
![](https://filescdn.proginn.com/3ce5fe8d0f22bf983e202dc1d0b5cd82/938a3fb23ef779662865b2c15fe396b4.webp)
![](https://filescdn.proginn.com/a9d2b018e68e0018369fd80d385eba2f/9206f7e9f1e1791a9c89c6c6f152f783.webp)
![](https://filescdn.proginn.com/0caa7e4ed24634e465ffb523c3d711ff/d6ccce6033789faf40a1248200559e80.webp)
![](https://filescdn.proginn.com/cb4f96e58959a9fa4fae06ce10b4615a/5b04de8e632c92fbdf8c5e22507a8626.webp)
![](https://filescdn.proginn.com/1db27ca31fae59d7560af71035b0332c/a05ced65014f9f5093b39b999235894b.webp)
![](https://filescdn.proginn.com/5c5ebfc555cbf66c8d6786b5052840f3/965da22b82f5115d488bbdf061747114.webp)
![](https://filescdn.proginn.com/5a8559da09de5125be81bfe7fb9ec63f/58483a2fe03e6bf71c960f87d94b054c.webp)
![](https://filescdn.proginn.com/8c4396ee347743f8d0d258e159007c5a/ac7a6d2d9d9aaeb4de1a612e74f623f2.webp)
![](https://filescdn.proginn.com/7e5e08912c176f70014f0b65cb1a0618/64d44287b213bdc5515b89dd47b3e783.webp)
![](https://filescdn.proginn.com/1915981b10cbf389d6bef370ae5155b0/871e897829adafcf717e218d57b505b1.webp)
![](https://filescdn.proginn.com/3df848dff1c1d9b4625307b5c084d63b/562ef1136b8883ece57b4d7dd829e155.webp)
![](https://filescdn.proginn.com/12cb20fe628c1a849ef8b65296bf3af9/cbf29533835b71577240d20e5e2639ad.webp)
![](https://filescdn.proginn.com/0b95e7d4bec1ca175597bc12ac395325/af498affab64bb29ab8ef33539cdb518.webp)
![](https://filescdn.proginn.com/3b9102ab511c86140f4545c2eb6b27a2/a1b2c28b91149ff988fd78ecb52c0c81.webp)
![](https://filescdn.proginn.com/b799c82919de0430ee87677cb3e9d1b1/0e0b8e698f4db7d09ddc0ea8a34f8948.webp)
![](https://filescdn.proginn.com/3c9e67045d26fd4215e55c866117e967/e10f9522a0729452c94e779d135b3f5d.webp)
![](https://filescdn.proginn.com/eaec2feb30752f62b63991898174f5f1/51da3c0c84d74ab6a6aa6e56cb6ba7a3.webp)
![](https://filescdn.proginn.com/408832bf39a9374a6d0ecf5bdcd3bbce/60ba00ddaac596de94fc16ee578fa31b.webp)
![](https://filescdn.proginn.com/15dbbbecd226fe09769dc08818609c93/77563d7d996cc05187ee2a0ef4d1afcb.webp)
![](https://filescdn.proginn.com/bc9b882e604989a3e95c4ba74a5e1bd1/2fbf84bd4a83accbf69d742a90c79075.webp)
//剩余蛋糕数量
static int leftCakes[];
//蛋糕总量(不是数量,而是大小之和)
static int totalCake = 0;
//浪费蛋糕量
static int lostCake = 0;
static boolean canFeed(int[] mouths, int monthIndex, int sum)
{
if(monthIndex<=0) {
//递归边界
return true;
}
//如果 蛋糕总量-浪费蛋糕量 小于当前的需求量,直接返回false,即无法满足
if(totalCake - lostCake < sum) {
return false;
}
//从小到大遍历蛋糕
for(int i=0;i<leftCakes.length; i++) {
if (leftCakes[i] >= mouths[monthIndex]) {
//找到并吃掉匹配的蛋糕
leftCakes[i] -= mouths[monthIndex];
//剩余蛋糕小于最小的需求,变为浪费蛋糕
if (leftCakes[i] < mouths[1]){
lostCake += leftCakes[i];
}
//继续递归,试图满足mid下标之前的需求
if (canFeed(mouths, monthIndex-1, sum)) {
return true;
}
//无法满足需求,蛋糕状态回滚
if (leftCakes[i] < mouths[1]) {
lostCake -= leftCakes[i];
}
leftCakes[i] += mouths[monthIndex];
}
}
return false;
}
public static int findMaxFeed(int[] cakes, int[] mouths){
//蛋糕升序排列,并把0下标空出
int[] cakesTemp = Arrays.copyOf(cakes, cakes.length+1);
Arrays.sort(cakesTemp);
for(int cake: cakesTemp){
totalCake += cake;
}
//顾客胃口升序排列,并把0下标空出
int[] mouthsTemp = Arrays.copyOf(mouths, mouths.length+1);
Arrays.sort(mouthsTemp);
leftCakes = new int[cakes.length+1];
//需求之和(下标0的元素是0个人的需求之和,下标1的元素是第1个人的需求之和,下标2的元素是第1,2个人的需求之和.....)
int[] sum = new int[mouths.length+1];
for(int i=1;i<=mouths.length;i++) {
sum[i] = sum[i - 1] + mouthsTemp[i];
}
//left和right用于计算二分查找的“中点”
int left=1,right=mouths.length;
//如果胃口总量大于蛋糕总量,right指针左移
while(sum[right]> totalCake){
right--;
}
//中位指针,用于做二分查找
int mid=((left+right)>>1);
while(left<=right)
{
//重置剩余蛋糕数组
leftCakes = Arrays.copyOf(cakesTemp, cakesTemp.length);
//重置浪费蛋糕量
lostCake =0;
//递归寻找满足需求的临界点
if(canFeed(mouthsTemp, mid, sum[mid])){
left=mid+1;
} else {
right = mid - 1;
}
mid=((left+right)>>1);
}
//最终找到的是刚好满足的临界点
return mid;
}
public static void main(String[] args) {
int[] cakes = new int[]{3,5,15,17,25};
int[] mouths = new int[]{2,5,7,9,12,14,20};
int maxFeed = findMaxFeed(cakes, mouths);
System.out.println("最大满足顾客数:" + maxFeed);
}
主流程方法findMaxFeed,执行各种初始化,控制二分查找流程。 方法canFeed,用于检验某一位置之前的顾客是否能被给定蛋糕满足。 数组leftCakes,用于临时存储剩余的蛋糕大小,每次重新设置中间下标时,这个数组需要被重置。
![](https://filescdn.proginn.com/1090807a79cfb58b779098d2aecda5fa/9487427ed691e138de8e37cdcc17f0c9.webp)
![](https://filescdn.proginn.com/faa95b75f56aab384accafda33a2ebc7/2dcfd109407007ceba3935afce6b96a9.webp)
![](https://filescdn.proginn.com/8a51a80f75441c4547f09a5775c6afdd/38c8db0f1ec7bf2268a492bfafdbae82.webp)
![](https://filescdn.proginn.com/b80de648caf85b5d873e47e07deea8ea/5accb3494bce00f96364d35e068b3280.webp)
延伸阅读👇
延伸阅读《算法导论》
评论