字节跳动19春招研发笔试过河问题 (智力题)

ゝ一纸荒年。 2022-02-19 00:07 309阅读 0赞

### 字节跳动19春招研发笔试 ###

*  前言
 *  题意
 *  我的思路 (错误思路)
 *   *  反例
 *  (应该是) 正确的思路
 *  (应该是) 正确的代码
 *  总结
 *  附录 (一): 笔试的错误代码 (只通过 11%)

# 前言 #

这道题否定了我的智力.

# 题意 #

n 个人  a 1 , a 2 . . . a n a\_1, a\_2 ... a\_n a1,a2...an 过河, 每个人  a i a\_i ai 都有一个  w i w\_i wi  
只有一艘船  
**每次过河船上最多装3人, 最少装2人**  
每次过河的时间是船上  w i w\_i wi 的最大值  
求最短过河时间.

# 我的思路 (错误思路) #

因为每次送完3个人到对岸之后, 要回来两个人摆渡, 那么我就选择  w i w\_i wi 最小的两个人作为摆渡人, 这样就使得每次回来的代价最小.  
概括起来就是:  
最轻的两个人永远在船上, 其他人每次过去一个.

## 反例 ##

上述思路的反例是, 如果  w = \{ 1 , 1 , 1 , 1 , 100 , 100 , 100 \} w = \\\{1, 1, 1, 1, 100, 100, 100\\\} w=\{ 1,1,1,1,100,100,100\}  
那么上述方法的代价是 100 + 1 + 100 + 1 + 100 + 1 + 1 + 1 = 305  
然而存在一个更优方法:  
 \{ 1 , 1 , 1 \} \\\{1, 1, 1\\\} \{ 1,1,1\} 过河  
 \{ 1 , 1 \} \\\{1, 1\\\} \{ 1,1\} 回来  
 \{ 1 , 1 , 1 \} \\\{1, 1, 1\\\} \{ 1,1,1\} 过河  
 \{ 1 , 1 \} \\\{1, 1\\\} \{ 1,1\} 回来  
 \{ 100 , 100 , 100 \} \\\{100, 100, 100\\\} \{ 100,100,100\} 过河  
 \{ 1 , 1 \} \\\{1, 1\\\} \{ 1,1\}回来  
 \{ 1 , 1 , 1 \} \\\{1, 1, 1\\\} \{ 1,1,1\} 过河  
 \{ 1 , 1 \} \\\{1, 1\\\} \{ 1,1\} 回来  
 \{ 1 , 1 , 1 \} \\\{1, 1, 1\\\} \{ 1,1,1\} 过河  
这样的代价是 108

# (应该是) 正确的思路 #

*  如果剩下 2 ~ 3 个人, 直接过去
 *  如果还有 4 个人, 最轻的两个永远在船上, 送最重的两个过去

接下来的情景中, 为了方便, 将人按照代价从小到大分别命名为 A, B, C … X, Y, Z,  
即 A 是代价最小的, C 是代价第三小的, Y 是代价第二大的, Z 是代价最大的.  
类比于 Linux 重定向操作, *“ABC >”* 表示 ABC 过河, *“AB <”* 表示 AB 摆渡回来.

*  如果还有 5 个人, 有两种方案:
    
     *  方案一: ABX >, AB <, ABY >, AB <, ABZ >. 总代价 2B + X + Y + Z
     *  方案二: ABX >, AB <, AYZ >, AX <, ABX >. 总代价 B + 3X + Z
 *  如果还有 6 个人, 有两种方案:
    
     *  方案一: ABX >, AB <, ABY >, AB <, ABZ >, AB <, ABC, 总代价 3B + C + X + Y + Z
     *  方案二: ABC >, AB <, ABX >, AB <, AYZ >, AC <, ABC >, 总代价 2B + 3C + X + Z
 *  如果还剩 7 个人及以上, 有三种方案可以每一次把3个最重的人送过去:
    
     *  方案一: ABC >, AB <, ABD >, AB <, XYZ >, CD <. 总代价 2B + C + D + Z
     *  方案二: ABZ >, AB <, ABY >, AB <, ABX >, AB <. 总代价 3B + X + Y + Z
     *  方案三: ABC >, AB <, AYZ >, AC <, ABX >, AB <. 总代价 2B + 2C + Y + Z

至于方案是怎么来的, 当然是自己想出来的…

# (应该是) 正确的代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int a[100001];
    int head, tail;
    int n;
    
    int compare(const void*a, const void*b) { 
    	return *(int*)a - *(int*)b;
    }
    
    int min(int a, int b) { 
    	return (a < b) ? a : b;
    }
    
    int main() { 
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) scanf("%d", a + i);
    	qsort(a, n, sizeof(int), compare);
    	tail = n - 1;
    	int left = n;
    	int ans = 0;
    	while (left > 6) { 
    		int planA = a[head + 2] + 2 * a[head + 3];
    		int planB = 3 * a[head + 1] + a[tail - 2] + a[tail - 1];
    		int planC = 2 * a[head + 2] + a[tail - 1];
    		ans += min(min(planA, planB), planC);
    		tail -= 3;
    		left -= 3;
    	}
    	if (left == 6) { 
    		int planA = 2 * a[head + 2];
    		int planB = a[head + 1] + a[tail - 1];
    		ans += min(planA, planB) + 2 * a[head + 1] + a[head + 2] + a[tail - 2] + a[tail];
    	} else if (left == 5) { 
    		int planA = a[head + 1] + a[tail - 1];
    		int planB = 2 * a[head + 2];
    		ans += min(planA, planB) + a[head + 1] + a[head + 2] + a[tail];
    	} else if (left == 4){ 
    		ans += a[head + 1] + a[tail] + a[tail - 1];
    	} else { 
    		// no possible
    	}
    	printf("%d\n", ans);
    }

# 总结 #

这道题虽然从来没出现过, 但是有一道类似的题 [\[poj 1700 Crossing River\]][poj 1700 Crossing River], 它是最多坐两个人最少坐一个人, 二者的思路是一样的.  
这个题出的是真的好, 确实是一个牛逼的智商筛选器.  
学!

# 附录 (一): 笔试的错误代码 (只通过 11%) #

#include <stdio.h>
    #include <stdlib.h>
    int a[100001];
    
    int compare(const void* a, const void* b) { 
        return *(int*)a - *(int*)b;
    }
    
    int main() { 
        int testcase;
        scanf("%d", &testcase);
        while (testcase--) { 
            int n;
            scanf("%d", &n);
            for (int i = 0; i < n; i++) scanf("%d", a + i);
            qsort(a, n, sizeof(int), compare);
            long result = 0;
            int left = n;
            if (left > 3) { 
                result += a[left-1];
                while (left > 3) { 
                    result += a[left - 2] + a[1];
                    left--;
                }
            } else { 
                result += a[left-1];
            }
            printf("%ld\n", result);
        }
    }

[poj 1700 Crossing River]: http://poj.org/problem?id=1700