2017年，完美世界c/c++ 夏季实习面试题 只有俩道编程题，但是我都没有accept，贴出我的答案 和交卷之后自己想的答案，希望得到一个不一样的想法。

---

1. 小明要持续打卡，但是呢上班又很没有意思，所以给自己找了一件事情做

那就是学习做菜，第i道，需要a[i]个单位的肉。但是肉是一整块的，每次切都 需要消耗小明的活力，消耗活力等于肉的大小（单位）。小明的刀法很好每 一次都可以切下来需要的肉。请问做n道菜，小明最少需要多少活力。

输入

3 /* 总共有多少道菜 */ 8 /* 第一道菜 需要8单位的肉 */ 5 8

输出

34

我的解答 通过率10% 使用c语言

我的想法是，每次需要消耗的活力是肉的单位大小，那每次切去最大单位的肉

消耗的活力肯定是最小的吧，所以排序之后，肉的总单位从后往前减去排序后的每道 菜需要的肉。这样得到的肯定是最小活力，但是就是不对，现在还没有想明白呢。

#include <stdio.h> #include <string.h> void Bublesort(int a[],int n) { int i,j,k; for(j=0;j<n-1;j++) { for(i=0;i<n-j-1;i++) { if(a[i]>a[i+1]) { k=a[i]; a[i]=a[i+1]; a[i+1]=k; } } } } int main() { int n; scanf("%d", &n); int array[n]; int index = 0; int result = 0; while(index < n) { scanf("%d", &array[index++]); result += array[index-1]; } Bublesort(array, n); n = 0; while(--index > 0) { n = n + result ; result -= array[index]; } printf("%d\n", n); }

2. 小明一不小心回到了2015年，而且记得未来n天的股票走势图，但是

害怕股票监管局的调查，只能有一个买入和卖出的机会，选出小明哪天 买入 ，哪天卖出可以得到最大收益。（相同的收益，最晚买入和最早卖出 是最佳收益，如果没有收益输出-1，-1.），天数从0开始。

输入

3 /* 知道的未来n天股票走势 */ 1 /* 第0天股票价格 */ 5 /* 第1天股票价格 */ 3 /* 第2天股票价格 */

输出

0,1

我的代码(提交的代码）通过率87%

想法

把股票按生序排序，，然后排除股票价格一样的情况

然后把最小值和原数组进行对比，找到最晚的最小值，如果有 相同的最小值的话。把最大值和原数组进行对比，找到第一个。 这样就满足了最晚买入和最早卖出的原则。但是没有考虑到如果 5 1 3 ，1 3 5 ；这种情况，假如第一天就是最高价格，这样我 的就直接输出-1，,1其实，1 3 才是最佳收益啊，我就是忽略了 这种情况。我自己觉得，所以才有了下面的代码2。

代码1

#include <stdio.h> #include <string.h> void Bublesort(int a[],int n) { int i,j,k; for(j=0;j<n-1;j++) { for(i=0;i<n-j-1;i++) { if(a[i]>a[i+1]) { k=a[i]; a[i]=a[i+1]; a[i+1]=k; } } } } void maxBT(int[] a, int []b, int length,int l, int r) { for(index = 0; index < n; index++) if (array_cp[0] == array_a[index]) buy = index; for(index = 0; index < n; index++) if (array_cp[n-1] == array_a[index]) { out = index; break; } if( buy > out ) { printf("%d,%d\n", -1, -1); return; } } void main() { int n; scanf("%d", &n); int array_a[n]; int array_cp[n]; int index = 0; int buy = -1; int out = -1; while(index < n) { scanf("%d", array_cp+index); array_a[index] = array_cp[index]; index++; } Bublesort(array_cp, n); if(array_cp[n-1] == array_cp[0]) { printf("%d,%d\n", buy, out); return; } printf("%d,%d\n", buy, out); return ;

我的代码(交卷又想了想重新写的)

想法

因为存在，股票最大值 和最小值 在最前面或者最后这种情况，所以需要

处理这种情况，知道找到最佳收益，这样的话就需要递归处理了，毕竟不知道 这种情况会出现多少次。刚好听了别人对这道题的解法所以就写了出来。 就是暴力求解法，把第一天和后面的每一天都比较找到最大的收益然后 接着把第二天和后面的每一天都进行比较找最大收益。这样就不存在递归情况 而且时间复杂度也就是冒泡排序的复杂度O(n^2). 最后需要考虑一下，最小间隔 就是最佳收益，如果存在相同的时间间隔，那就取栈的前面就可以了。相同时间 间隔，越早得到最大收益，风险越小，属于最佳收益。我们是这样想法，至于对不对 就不知道了。

代码2

#include <stdio.h> #include <string.h> int stack[10]; int top = -1; void push(int a) { stack[++top] = a; } int pop() { return stack[top--]; } void Bublesort(int a[], int n) { int i,j,k; int max = 0; int m = 1; for(j=0;j<n-1;j++) { for(i=j+1;i<n;i++) { m = a[i] - a[j]; if (max == m) { push(j); push(i); } if (max < m) { top = -1; max = m; push(j); push(i); } } } } void main() { int n; scanf("%d", &n); int array_a[n]; int array_cp[n]; int index = 0; int buy = -1; int out = -1; while(index < n) { scanf("%d", array_cp+index++); } Bublesort(array_cp, n); if (top == -1) /* stack is empty */ { printf("%d,%d\n", buy, out); return; } /* for(index=0; index<=top; index++) printf("%d ", stack[index]); printf("\n"); */ int count = 0; int min_length = 655; int length; int result = -1; for (index = top; index >0; index-=2) { length = stack[index] - stack[index-1]; if (min_length == length) { count++; result = index; } if (min_length > length) { min_length = length; count = 0; result = index; } } printf("%d,%d\n", stack[result-1], stack[result]); return ; }